A LINEAR-TIME ALGORITHM FOR PREDICTING FUNCTIONAL ANNOTATIONS FROM PPI NETWORKS
Abstract
Recent proteome-wide screening efforts have made available genome-wide, high-throughput protein–protein interaction (PPI) maps for several model organisms. This has enabled the systematic analysis of PPI networks, which has become one of the primary challenges for the systems biology community. Here, we address the problem of predicting the functional classes of proteins (i.e. GO annotations) based solely on the structure of the PPI network. We present a maximum likelihood formulation of the problem and the corresponding learning and inference algorithms. The time complexity of both algorithms is linear in the size of the PPI network, and our experimental results show that their accuracy in functional prediction outperforms current existing methods.
A preliminary version of this work was presented at the 7th International Workshop on Data Mining in Bioinformatics, San Jose, CA, and included in its Proceedings (2007).
References
- Nature 403(6770), 623 (2000). Crossref, Medline, Google Scholar
- Science 302(5651), 1727 (2003), DOI: 10.1126/science.1090289. Crossref, Medline, Google Scholar
- Genome. Res. 15(3), 376 (2005), DOI: 10.1101/gr.2659105. Crossref, Medline, Google Scholar
- Science 303, 540 (2004), DOI: 10.1126/science.1091403. Crossref, Medline, Google Scholar
- Nature 437, 1173 (2005), DOI: 10.1038/nature04209. Crossref, Medline, Google Scholar
- Nature 409, 211 (2001), DOI: 10.1038/35051615. Crossref, Medline, Google Scholar
- Proc. Natl. Acad. Sci. USA 101(9), 2888 (2004), DOI: 10.1073/pnas.0307326101. Crossref, Medline, Google Scholar
- Nat. Biotechnol. 21, 697 (2003), DOI: 10.1038/nbt825. Crossref, Medline, Google Scholar
B. S. Srinivasan , Integrated protein interaction networks for 11 microbes, Proceedings of ACM RECOMB (2006) pp. 1–14. Google ScholarE. Nabieva , Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps, Proceedings of ISMB (2005) pp. 302–310. Google Scholar- Nat. Biotechnol. 18, 1257 (2000), DOI: 10.1038/82360. Crossref, Medline, Google Scholar
- Yeast 18(6), 523 (2001), DOI: 10.1002/yea.706. Crossref, Medline, Google Scholar
- Bioinformatics 22, 1623 (2006), DOI: 10.1093/bioinformatics/btl145. Crossref, Medline, Google Scholar
- Bioinformatics 20(6), 895 (2004), DOI: 10.1093/bioinformatics/btg500. Crossref, Medline, Google Scholar
- J. Comput. Biol. 10(6), 947 (2003), DOI: 10.1089/106652703322756168. Crossref, Medline, Google Scholar
- J. Comput. Biol. 11(2/3), 463 (2004), DOI: 10.1089/1066527041410346. Crossref, Medline, Google Scholar
- Bioinformatics 19(1), i197 (2003), DOI: 10.1093/bioinformatics/btg1026. Crossref, Google Scholar
A. Jaimovich , Towards an integrated protein–protein interaction network, Proceedings of ACM RECOMB (2005) pp. 14–30. Google Scholar- Nucleic. Acids. Res. 32, D449 (2004), DOI: 10.1093/nar/gkh086. Crossref, Medline, Google Scholar
- Nat. Genet. 25, 25 (2000). Crossref, Medline, Google Scholar
-
V. V. Vazirani , Approximation Algorithms ( Springer-Verlag , New York , 2001 ) . Google Scholar - Nature 417(6887), 399 (2002), DOI: 10.1038/417797a. Crossref, Medline, Google Scholar
- Pac. Symp. Biocomput. 140 (2003). Medline, Google Scholar
Q. Yang , Evolution versus intelligent design: Comparing the topology of protein–protein interaction networks to the Internet, Proceedings of IEEE Computational Systems Bioinformatics Conference (CSB'06) (2006) pp. 299–310. Google Scholar
