title: Protein complex prediction via verifying and reconstructing the topology of domain-domain interactions.
abstract: BACKGROUND
  High-throughput methods for detecting protein-protein interactions enable us to obtain large interaction networks, and also allow us to computationally identify the associations of proteins as protein complexes. Although there are methods to extract protein complexes as sets of proteins from interaction networks, the extracted complexes may include false positives because they do not account for the structural limitations of the proteins and thus do not check that the proteins in the extracted complex can simultaneously bind to each other. In addition, there have been few searches for deeper insights into the protein complexes, such as of the topology of the protein-protein interactions or into the domain-domain interactions that mediate the protein interactions.
  
  
  RESULTS
  Here, we introduce a combinatorial approach for prediction of protein complexes focusing not only on determining member proteins in complexes but also on the DDI/PPI organization of the complexes. Our method analyzes complex candidates predicted by the existing methods. It searches for optimal combinations of domain-domain interactions in the candidates based on an assumption that the proteins in a candidate can form a true protein complex if each of the domains is used by a single protein interaction. This optimization problem was mathematically formulated and solved using binary integer linear programming. By using publicly available sets of yeast protein-protein interactions and domain-domain interactions, we succeeded in extracting protein complex candidates with an accuracy that is twice the average accuracy of the existing methods, MCL, MCODE, or clustering coefficient. Although the configuring parameters for each algorithm resulted in slightly improved precisions, our method always showed better precision for most values of the parameters.
  
  
  CONCLUSIONS
  Our combinatorial approach can provide better accuracy for prediction of protein complexes and also enables to identify both direct PPIs and DDIs that mediate them in complexes.
authors.affiliation: Institute for Advanced Biosciences, Keio University, 403-1, Daihoji, Tsuruoka, Yamagata 997-0017, Japan.
authors.forename: Yosuke
authors.initials: Y
authors.lastname: Ozawa
authors.forename: Rintaro
authors.initials: R
authors.lastname: Saito
authors.forename: Shigeo
authors.initials: S
authors.lastname: Fujimori
authors.forename: Hisashi
authors.initials: H
authors.lastname: Kashima
authors.forename: Masamichi
authors.initials: M
authors.lastname: Ishizaka
authors.forename: Hiroshi
authors.initials: H
authors.lastname: Yanagawa
authors.forename: Etsuko
authors.initials: E
authors.lastname: Miyamoto-Sato
authors.forename: Masaru
authors.initials: M
authors.lastname: Tomita
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D046912:Multiprotein Complexes / Q000737:chemistry*; D011382:Programming, Linear; D054730:Protein Interaction Domains and Motifs; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins / Q000737:chemistry* / Q000378:metabolism*; D020798:Two-Hybrid System Techniques
chemical_list: D046912:Multiprotein Complexes; D011506:Proteins