title: Predicting protein-protein interactions from protein domains using a set cover approach.
abstract: One goal of contemporary proteome research is the elucidation of cellular protein interactions. Based on currently available protein-protein interaction and domain data, we introduce a novel method, Maximum Specificity Set Cover (MSSC), for the prediction of protein-protein interactions. In our approach, we map the relationship between interactions of proteins and their corresponding domain architectures to a generalized weighted set cover problem. The application of a greedy algorithm provides sets of domain interactions which explain the presence of protein interactions to the largest degree of specificity. Utilizing domain and protein interaction data of S. cerevisiae, MSSC enables prediction of previously unknown protein interactions, links that are well supported by a high tendency of coexpression and functional homogeneity of the corresponding proteins. Focusing on concrete examples, we show that MSSC reliably predicts protein interactions in well-studied molecular systems, such as the 26S proteasome and RNA polymerase II of S. cerevisiae. We also show that the quality of the predictions is comparable to the Maximum Likelihood Estimation while MSSC is faster. This new algorithm and all data sets used are accessible through a Web portal at http://ppi.cse.nd.edu.
authors.affiliation: Department of Computer Science and Engineering, University of Notre Dame, IN 46556, USA. chuang1@nd.edu
authors.forename: Chengbang
authors.initials: C
authors.lastname: Huang
authors.forename: Faruck
authors.initials: F
authors.lastname: Morcos
authors.forename: Simon P
authors.initials: SP
authors.lastname: Kanaan
authors.forename: Stefan
authors.initials: S
authors.lastname: Wuchty
authors.forename: Danny Z
authors.initials: DZ
authors.lastname: Chen
authors.forename: Jesús A
authors.initials: JA
authors.lastname: Izaguirre
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D030562:Databases, Protein; D020869:Gene Expression Profiling; D020407:Internet; D016013:Likelihood Functions; D015233:Models, Statistical; D020411:Oligonucleotide Array Sequence Analysis; D046988:Proteasome Endopeptidase Complex / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D025941:Protein Interaction Mapping / Q000379:methods; D017434:Protein Structure, Tertiary; D011506:Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D040901:Proteomics / Q000379:methods*; D012319:RNA Polymerase II / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism
chemical_list: D011506:Proteins; D029701:Saccharomyces cerevisiae Proteins; D012319:RNA Polymerase II; D046988:Proteasome Endopeptidase Complex; C061553:ATP dependent 26S protease