{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T21:20:14Z","timestamp":1717708814161},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: In the last few years, a growing interest in biology has been shifting toward the problem of optimal information extraction from the huge amount of data generated via large-scale and high-throughput techniques. One of the most relevant issues has recently emerged that of correctly and reliably predicting the functions of a given protein with that of functions exploiting information coming from the whole network of proteins physically interacting with the functionally undetermined one. In the present work, we will refer to an \u2018observed\u2019 protein as the one present in the protein\u2013protein interaction networks published in the literature.<\/jats:p>\n               <jats:p>Methods: The method proposed in this paper is based on a message passing algorithm known as Belief Propagation, which accepts the network of protein's physical interactions and a catalog of known protein's functions as input, and returns the probabilities for each unclassified protein of having one chosen function. The implementation of the algorithm allows for fast online analysis, and can easily be generalized into more complex graph topologies taking into account hypergraphs, i.e. complexes of more than two interacting proteins.<\/jats:p>\n               <jats:p>Results: Benchmarks of our method are the two Saccharomyces cerevisiae protein\u2013protein interaction networks and the Database of Interacting Proteins. The validity of our approach is successfully tested against other available techniques.<\/jats:p>\n               <jats:p>Contact: \u00a0leone@isiosf.isi.it<\/jats:p>\n               <jats:p>Supplementary information: \u00a0http:\/\/isiosf.isi.it\/~pagnani<\/jats:p>","DOI":"10.1093\/bioinformatics\/bth491","type":"journal-article","created":{"date-parts":[[2004,9,18]],"date-time":"2004-09-18T00:13:19Z","timestamp":1095466399000},"page":"239-247","source":"Crossref","is-referenced-by-count":24,"title":["Predicting protein functions with message passing algorithms"],"prefix":"10.1093","volume":"21","author":[{"given":"Michele","family":"Leone","sequence":"first","affiliation":[{"name":"Institute for Scientific Interchange (ISI) Viale Settimio Severo 65, Turin, I-10133, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Pagnani","sequence":"additional","affiliation":[{"name":"Institute for Scientific Interchange (ISI) Viale Settimio Severo 65, Turin, I-10133, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2004,9,17]]},"reference":[{"key":"2023013107192785100_B1","doi-asserted-by":"crossref","unstructured":"Altschul, S.F., Madden, T.L., Schaffer, A.A., Zhang, J., Zhang, Z., Miller, W., Lipman, D.J. 1997Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res.253389\u20133402","DOI":"10.1093\/nar\/25.17.3389"},{"key":"2023013107192785100_B2","unstructured":"Deng, M., Zhang, K., Mehta, S., Chen, T., Sun, F. 2002Prediction of protein function using protein\u2013protein interaction data. Proceedings of the IEEE Computer Society Bioinformatics Conference (CSB'02) August 14\u201316, , Stanford, CA ,  pp. 197\u2013207"},{"key":"2023013107192785100_B3","unstructured":"Gavin, A.C., Bosche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J.M., Michon, A.M., Cruciat, C.M., et al. 2002Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature415141\u2013147"},{"key":"2023013107192785100_B4","unstructured":"Giot, L., Bader, J.S., Brouwer, C., Chaudhuri, A., Kuang, B., Li, Y., Hao, Y.L., Ooi, C.E., Godwin, B., Vitols, E., et al. 2003A protein interaction map of Drosophila melanogaster               . Science3021727\u20131736"},{"key":"2023013107192785100_B5","doi-asserted-by":"crossref","unstructured":"Hishigaki, H., Nakai, K., Ono, T., Tanigami, A., Tagaki, T. 2001Assessment of prediction accuracy of protein function from protein\u2013protein interaction data. Yeast18523\u2013531","DOI":"10.1002\/yea.706"},{"key":"2023013107192785100_B6","unstructured":"Ho, Y., Grubler, A., Heilbut, A., Bader, G.D., Moore, L., Adams, S.L., Millar, A., Taylor, P., Bennett, K., Boutilier, K., et al. 2002Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry. Nature415180\u2013183"},{"key":"2023013107192785100_B7","unstructured":"Hodgman, T. 2000A historical perspective on gene\/protein functional assignment. Bioinformatics1610\u201315"},{"key":"2023013107192785100_B8","doi-asserted-by":"crossref","unstructured":"Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M., Sakaki, Y. 2001A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc. Natl Acad. Sci. USA984569\u20134574","DOI":"10.1073\/pnas.061034498"},{"key":"2023013107192785100_B9","doi-asserted-by":"crossref","unstructured":"Jansen, R., Yu, H., Greenbaum, D., Kluger, Y., Krogan, N.J., Chung, S., Emili, A., Snyder, M., Greenbalt, J.F., Gerstein, M. 2003A Bayesian networks approach for predicting protein\u2013protein interactions from genomic data. Science302449\u2013453","DOI":"10.1126\/science.1087361"},{"key":"2023013107192785100_B10","doi-asserted-by":"crossref","unstructured":"Lappe, M. and Holm, L. 2004Unraveling protein interaction networks with near-optimal efficiency. Nat. Biotechnol.2298\u2013103","DOI":"10.1038\/nbt921"},{"key":"2023013107192785100_B11","doi-asserted-by":"crossref","unstructured":"Letovsky, S. and Kasif, S. 2003Predicting protein function from protein\/protein interaction data: a probabilistic approach. Bioinformatics19Suppl. 1,i197\u2013i204","DOI":"10.1093\/bioinformatics\/btg1026"},{"key":"2023013107192785100_B12","doi-asserted-by":"crossref","unstructured":"Marcotte, E.M., Pellegrini, M., Thompson, M.J., Yeates, T.O., Eisenberg, D. 1999A combined algorithm for genome-wide prediction of protein function. Nature40283\u201386","DOI":"10.1038\/47048"},{"key":"2023013107192785100_B13","doi-asserted-by":"crossref","unstructured":"Marcotte, E.M., Pellegrini, M., Ng, H.L., Rice, D.W., Yeates, T.O., Eisenberg, D. 1999Detecting protein functions and protein\u2013protein interactions from genome sequences. Science285751\u2013753","DOI":"10.1126\/science.285.5428.751"},{"key":"2023013107192785100_B14","doi-asserted-by":"crossref","unstructured":"M\u00e8zard, M. and Parisi, G. 2001The Bethe lattice spin glass revisited. Eur. Phys. J. B20217","DOI":"10.1007\/PL00011099"},{"key":"2023013107192785100_B15","unstructured":"Pearson, W.R. and Lipman, D.J. 1988Improved tools for biological sequence comparison. Proc. Natl Acad. Sci. USA852444\u20132448"},{"key":"2023013107192785100_B16","doi-asserted-by":"crossref","unstructured":"Samanta, M.P. and Liang, S. 2003Predicting protein functions from redundancies in large-scale protein interaction networks. Proc. Natl Acad. Sci. USA10012579\u201312583","DOI":"10.1073\/pnas.2132527100"},{"key":"2023013107192785100_B17","doi-asserted-by":"crossref","unstructured":"Schwikowski, B., Uetz, P., Fields, S. 2000A network of protein\u2013protein interactions in yeast. Nat. Biotechnol.181257\u20131261","DOI":"10.1038\/82360"},{"key":"2023013107192785100_B18","doi-asserted-by":"crossref","unstructured":"Uetz, P., Giot, L., Cagney, G., Mansfield, T.A., Judson, R.S., Knight, J.R., Lockshon, D., Narayan, V., Srinivasan, M., Pochart, P., et al. 2000A comprehensive analysis of protein\u2013protein interactions in Saccharomyces cerevisiae               . Nature403623\u2013627","DOI":"10.1038\/35001009"},{"key":"2023013107192785100_B19","doi-asserted-by":"crossref","unstructured":"Vazquez, A., Flammini, A., Maritan, A., Vespignani, A. 2003Global protein function prediction in protein\u2013protein interaction networks. Nat. Biotechnol.21697\u2013700","DOI":"10.1038\/nbt825"},{"key":"2023013107192785100_B20","unstructured":"Xenarios, I., Rice, D.W., Salwinski, L., Baron, M.K., Marcotte, E.M., Eisenberg, D. 2000DIP: the database of interacting proteins. Nucleic Acids Res.28289\u2013291"},{"key":"2023013107192785100_B21","doi-asserted-by":"crossref","unstructured":"Yeang, C.-H. and Jaakkola, T. 2003Physical network models and multi-source data integration. The Seventh Annual International Conference on Research in Computational Molecular Biology (RECOMB 2003) April 10\u201313, , Berlin","DOI":"10.1145\/640075.640117"},{"key":"2023013107192785100_B22","unstructured":"Yedidia, J., Freeman, W., Weiss, Y. Understanding Belief Propagation and Its Generalizations, Exploring Artificial Intelligence in the New Millennium2003 Elsevier Science & Technology Books"},{"key":"2023013107192785100_B23","doi-asserted-by":"crossref","unstructured":"Yook, S., Oltvai, Z., Barab\u00e1si, A.-L. 2004Functional and topological characterization of protein interaction networks. Proteomics4,  pp. 928\u2013942","DOI":"10.1002\/pmic.200300636"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/2\/239\/48961843\/bioinformatics_21_2_239.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/2\/239\/48961843\/bioinformatics_21_2_239.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T09:56:23Z","timestamp":1675158983000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/2\/239\/187186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9,17]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bth491","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2005,1,15]]},"published":{"date-parts":[[2004,9,17]]}}}