Motivation: Recent advances in high-throughput technologies have made it possible to investigate not only individual protein interactions but the association of these proteins in complexes. So far the focus has been on the prediction of complexes as sets of proteins from the experimental results. The modular substructure and the physical interactions within the protein complexes have been mostly ignored. Results: We present an approach for identifying the direct physical interactions and the subcomponent structure of protein complexes predicted from affinity purification assays. Our algorithm calculates the union of all maximum spanning trees from scoring networks for each protein complex to extract relevant interactions. In a subsequent step this network is extended to interactions which are not accounted for by alternative indirect paths. We show that the interactions identi- fied with this approach are more accurate in predicting experimentally derived physical interactions than baseline approaches. Based on these networks, the subcomponent structure of the complexes can be resolved more satisfactorily and subcomplexes can be identified. The usefulness of our method is illustrated on the RNA polymerases for which the modular substructure can be successfully reconstructed. Availability: A Java implementation of the prediction methods and supplementary material are available at http://www.bio.ifi.lmu.de/ Complexes/Substructures/.

The software suite for the prediction of physical interactions within protein complexes is based on the ProCope library (see Project website). ProCope binaries are distributed with this release.

To use the software library, download one of the archives and unzip. Provided are a commandline tool for predicting interactions with the MST and extended MST approach, the corresponding source code and the binaries for the ProCope library. After unzipping, just go in the directory created and type

 java -jar substructures.jar

to invoke the commandline tool. Parameters for the commandline tool are given in the README.txt file or printed if the commandline tool is used without parameters.