title: Protein complex prediction via improved verification methods using constrained domain-domain matching.
abstract: Identification of protein complexes within protein-protein interaction networks is one of the important objectives in functional genomics. Ozawa et al. proposed a verification method of protein complexes by introducing a structural constraint. In this paper, we propose an improved integer programming-based method based on the idea that a candidate complex should not be divided into many small complexes, and combination methods with maximal components and extreme sets. The results of computational experiments suggest that our methods outperform the method by Ozawa et al. We prove that the verification problems are NP-hard, which justifies the use of integer programming.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, Japan. tyoyo@kuicr.kyoto-u.ac.jp
authors.forename: Yang
authors.initials: Y
authors.lastname: Zhao
authors.forename: Morihiro
authors.initials: M
authors.lastname: Hayashida
authors.forename: Jose C
authors.initials: JC
authors.lastname: Nacher
authors.forename: Hiroshi
authors.initials: H
authors.lastname: Nagamochi
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: D000465:Algorithms; D001665:Binding Sites; D030562:Databases, Protein; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins / Q000737:chemistry / Q000378:metabolism*
chemical_list: D011506:Proteins