Comparing protein interaction networks via a graph match-and-split algorithm.
J Comput Biol
; 14(7): 892-907, 2007 Sep.
Article
em En
| MEDLINE
| ID: mdl-17803369
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/ approximately nmani/M-and-S/supplement.pdf.
Buscar no Google
Base de dados:
MEDLINE
Assunto principal:
Algoritmos
/
Proteínas
/
Mapeamento de Interação de Proteínas
Tipo de estudo:
Prognostic_studies
Limite:
Humans
Idioma:
En
Ano de publicação:
2007
Tipo de documento:
Article