Comparing Protein Interaction Networks via a Graph Match-and-Split Algorithm
- 1 September 2007
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 14 (7) , 892-907
Abstract
We present a method that compares the protein interaction networks of two species to detect functionally similar (conserved) protein modules between them. The method is based on an algorithm we developed to identify matching subgraphs between two graphs. Unlike previous network comparison methods, our algorithm has provable guarantees on correctness and efficiency. Our algorithm framework also admits quite general criteria that define when two subgraphs match and constitute a conserved module. We apply our method to pairwise comparisons of the yeast protein network with the human, fruit fly and nematode worm protein networks, using a lenient criterion based on connectedness and matching edges, coupled with a clustering heuristic. In evaluations of the detected conserved modules against reference yeast protein complexes, our method performs competitively with and sometimes better than two previous network comparison methods. Further, under some conditions (proper homolog and species selection), our method performs better than a popular single-species clustering method. Beyond these evaluations, we discuss the biology of a couple of conserved modules detected by our method. We demonstrate the utility of network comparison for transferring annotations from yeast proteins to human ones, and validate the predicted annotations. Supplemental text is available at www.cs.berkeley.edu/∼nmani/M-and-S/supplement.pdf.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Græmlin: General and robust alignment of multiple large interaction networksGenome Research, 2006
- Cross-species analysis of biological networks by Bayesian alignmentProceedings of the National Academy of Sciences, 2006
- GO::TermFinder—open source software for accessing Gene Ontology information and finding significantly enriched Gene Ontology terms associated with a list of genesBioinformatics, 2004
- Protein interaction networks from yeast to humanCurrent Opinion in Structural Biology, 2004
- UniProt: the Universal Protein knowledgebaseNucleic Acids Research, 2004
- An automated method for finding molecular complexes in large protein interaction networksBMC Bioinformatics, 2003
- Community structure in social and biological networksProceedings of the National Academy of Sciences, 2002
- Gene Ontology: tool for the unification of biologyNature Genetics, 2000
- Error correcting graph matching: on the influence of the underlying cost functionIEEE Transactions on Pattern Analysis and Machine Intelligence, 1999
- Evaluation of Gene Structure Prediction ProgramsGenomics, 1996