{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T12:09:49Z","timestamp":1776082189788,"version":"3.50.1"},"reference-count":49,"publisher":"Oxford University Press (OUP)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Recent advances in technology have dramatically increased the availability of protein\u2013protein interaction (PPI) data and stimulated the development of many methods for improving the systems level understanding the cell. However, those efforts have been significantly hindered by the high level of noise, sparseness and highly skewed degree distribution of PPI networks. Here, we present a novel algorithm to reduce the noise present in PPI networks. The key idea of our algorithm is that two proteins sharing some higher-order topological similarities, measured by a novel random walk-based procedure, are likely interacting with each other and may belong to the same protein complex.<\/jats:p>\n               <jats:p>Results: Applying our algorithm to a yeast PPI network, we found that the edges in the reconstructed network have higher biological relevance than in the original network, assessed by multiple types of information, including gene ontology, gene expression, essentiality, conservation between species and known protein complexes. Comparison with existing methods shows that the network reconstructed by our method has the highest quality. Using two independent graph clustering algorithms, we found that the reconstructed network has resulted in significantly improved prediction accuracy of protein complexes. Furthermore, our method is applicable to PPI networks obtained with different experimental systems, such as affinity purification, yeast two-hybrid (Y2H) and protein-fragment complementation assay (PCA), and evidence shows that the predicted edges are likely bona fide physical interactions. Finally, an application to a human PPI network increased the coverage of the network by at least 100%.<\/jats:p>\n               <jats:p>Availability: \u00a0www.cs.utsa.edu\/\u223cjruan\/RWS\/.<\/jats:p>\n               <jats:p>Contact: \u00a0Jianhua.Ruan@utsa.edu<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts688","type":"journal-article","created":{"date-parts":[[2012,12,13]],"date-time":"2012-12-13T01:44:55Z","timestamp":1355363095000},"page":"355-364","source":"Crossref","is-referenced-by-count":179,"title":["A novel link prediction algorithm for reconstructing protein\u2013protein interaction networks by topological similarity"],"prefix":"10.1093","volume":"29","author":[{"given":"Chengwei","family":"Lei","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Texas at San Antonio, San Antonio, TX 78249, USA"}]},{"given":"Jianhua","family":"Ruan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at San Antonio, San Antonio, TX 78249, USA"}]}],"member":"286","published-online":{"date-parts":[[2012,12,11]]},"reference":[{"key":"2023012810230735700_bts688-B1","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.1101\/gr.2203804","article-title":"Predicting protein complex membership using probabilistic network reliability","volume":"14","author":"Asthana","year":"2004","journal-title":"Genome Res."},{"key":"2023012810230735700_bts688-B2","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1038\/nbt1002-991","article-title":"Analyzing yeast protein-protein interaction data obtained from different sources","volume":"20","author":"Bader","year":"2002","journal-title":"Nat. Biotechnol."},{"key":"2023012810230735700_bts688-B3","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1186\/1471-2105-7-488","article-title":"Evaluation of clustering algorithms for protein-protein interaction networks","volume":"7","author":"Brohee","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012810230735700_bts688-B4","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1186\/1471-2105-11-421","article-title":"Microarray meta-analysis database (m2db): a uniformly pre-processed, quality controlled, and manually curated human clinical microarray database","volume":"11","author":"Cheng","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012810230735700_bts688-B5","doi-asserted-by":"crossref","first-page":"1623","DOI":"10.1093\/bioinformatics\/btl145","article-title":"Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions","volume":"22","author":"Chua","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012810230735700_bts688-B6","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1038\/msb4100180","article-title":"Network-based classification of breast cancer metastasis","volume":"3","author":"Chuang","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023012810230735700_bts688-B7","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1093\/bib\/5.1.9","article-title":"Saccharomyces genome database: underlying principles and organisation","volume":"5","author":"Dwight","year":"2004","journal-title":"Brief. Bioinform."},{"key":"2023012810230735700_bts688-B8","doi-asserted-by":"crossref","first-page":"e19349","DOI":"10.1371\/journal.pone.0019349","article-title":"Global geometric affinity for revealing high fidelity protein interaction network","volume":"6","author":"Fang","year":"2011","journal-title":"PLoS ONE"},{"key":"2023012810230735700_bts688-B9","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1109\/TKDE.2007.46","article-title":"Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation","volume":"19","author":"Fouss","year":"2007","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2023012810230735700_bts688-B10","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1080\/01621459.1983.10478008","article-title":"A method for comparing two hierarchical clusterings","volume":"78","author":"Fowlkes","year":"1983","journal-title":"J. Am. Stat. Assoc."},{"key":"2023012810230735700_bts688-B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/cmb.2009.0023","article-title":"Bootstrapping the interactome: unsupervised identification of protein complexes in yeast","volume":"16","author":"Friedel","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012810230735700_bts688-B12","doi-asserted-by":"crossref","first-page":"4241","DOI":"10.1091\/mbc.11.12.4241","article-title":"Genomic expression programs in the response of yeast cells to environmental changes","volume":"11","author":"Gasch","year":"2000","journal-title":"Mol. Biol. Cell"},{"key":"2023012810230735700_bts688-B13","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1038\/nature04532","article-title":"Proteome survey reveals modularity of the yeast cell machinery","volume":"440","author":"Gavin","year":"2006","journal-title":"Nature"},{"key":"2023012810230735700_bts688-B14","doi-asserted-by":"crossref","first-page":"16698","DOI":"10.1074\/jbc.M213109200","article-title":"Mnd2 and swm1 are core subunits of the saccharomyces cerevisiae anaphase-promoting complex","volume":"278","author":"Hall","year":"2003","journal-title":"J. Biol. Chem."},{"key":"2023012810230735700_bts688-B15","doi-asserted-by":"crossref","first-page":"e1000782","DOI":"10.1371\/journal.pgen.1000782","article-title":"Genome-wide association data reveal a global map of genetic interactions among protein complexes","volume":"5","author":"Hannum","year":"2009","journal-title":"PLoS Genet."},{"key":"2023012810230735700_bts688-B16","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/nature02555","article-title":"Evidence for dynamically organized modularity in the yeast protein-protein interaction network","volume":"430","author":"Han","year":"2004","journal-title":"Nature"},{"key":"2023012810230735700_bts688-B17","doi-asserted-by":"crossref","first-page":"e1000353","DOI":"10.1371\/journal.pcbi.1000353","article-title":"A dynamic network approach for the study of human phenotypes","volume":"5","author":"Hidalgo","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023012810230735700_bts688-B18","doi-asserted-by":"crossref","first-page":"e214","DOI":"10.1371\/journal.pcbi.0030214","article-title":"Where have all the interactions gone? Estimating the coverage of two-hybrid protein interaction maps","volume":"3","author":"Huang","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023012810230735700_bts688-B19","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1101\/gr.071852.107","article-title":"Protein networks in disease","volume":"18","author":"Ideker","year":"2008","journal-title":"Genome Res."},{"key":"2023012810230735700_bts688-B20","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1038\/35075138","article-title":"Lethality and centrality in protein networks","volume":"411","author":"Jeong","year":"2001","journal-title":"Nature"},{"key":"2023012810230735700_bts688-B21","doi-asserted-by":"crossref","first-page":"D767","DOI":"10.1093\/nar\/gkn892","article-title":"Human protein reference database\u20132009 update","volume":"37","author":"Keshava Prasad","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012810230735700_bts688-B22","doi-asserted-by":"crossref","first-page":"e1001095","DOI":"10.1371\/journal.pcbi.1001095","article-title":"Identifying causal genes and dysregulated pathways in complex diseases","volume":"7","author":"Kim","year":"2011","journal-title":"PLoS Comput. Biol."},{"key":"2023012810230735700_bts688-B23","doi-asserted-by":"crossref","first-page":"3013","DOI":"10.1093\/bioinformatics\/bth351","article-title":"Protein complex prediction via cost-based clustering","volume":"20","author":"King","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012810230735700_bts688-B24","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1038\/nature04670","article-title":"Global landscape of protein complexes in the yeast saccharomyces cerevisiae","volume":"440","author":"Krogan","year":"2006","journal-title":"Nature"},{"key":"2023012810230735700_bts688-B25","doi-asserted-by":"crossref","first-page":"e1000454","DOI":"10.1371\/journal.pcbi.1000454","article-title":"Geometric de-noising of protein-protein interaction networks","volume":"5","author":"Kuchaiev","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023012810230735700_bts688-B26","doi-asserted-by":"crossref","first-page":"e136","DOI":"10.1093\/nar\/gkn619","article-title":"Protein networks markedly improve prediction of subcellular localization in multiple eukaryotic species","volume":"36","author":"Lee","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012810230735700_bts688-B27","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1093\/bioinformatics\/btl581","article-title":"Network neighborhood analysis with the multi-node topological overlap measure","volume":"23","author":"Li","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012810230735700_bts688-B28","first-page":"1","article-title":"Random walks on graphs: a survey","volume":"2","author":"Lov\u00e1sz","year":"1993","journal-title":"Combinatorics, Paul Erd\u0151s is Eighty"},{"key":"2023012810230735700_bts688-B29","doi-asserted-by":"crossref","first-page":"1150","DOI":"10.1016\/j.physa.2010.11.027","article-title":"Link prediction in complex networks: a survey","volume":"390","author":"L\u00fc","year":"2011","journal-title":"Physica A"},{"key":"2023012810230735700_bts688-B30","first-page":"577","article-title":"Comparing clusterings: an axiomatic view","author":"Meila","year":"2005"},{"key":"2023012810230735700_bts688-B31","doi-asserted-by":"crossref","first-page":"D169","DOI":"10.1093\/nar\/gkj148","article-title":"MIPS: analysis and annotation of proteins from whole genomes in 2005","volume":"34","author":"Mewes","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023012810230735700_bts688-B32","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1002\/bies.201000044","article-title":"Protein-protein interactions: making sense of networks via graph-theoretic modeling","volume":"33","author":"Przulj","year":"2011","journal-title":"Bioessays"},{"key":"2023012810230735700_bts688-B33","doi-asserted-by":"crossref","first-page":"2658","DOI":"10.1073\/pnas.0400054101","article-title":"Defining and identifying communities in networks","volume":"101","author":"Radicchi","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012810230735700_bts688-B34","first-page":"470","article-title":"Identification and evaluation of weak community structures in networks","author":"Ruan","year":"2006"},{"key":"2023012810230735700_bts688-B35","doi-asserted-by":"crossref","first-page":"016104","DOI":"10.1103\/PhysRevE.77.016104","article-title":"Identifying network community structures with a high resolution","volume":"77","author":"Ruan","year":"2008","journal-title":"Phys. Rev. E"},{"key":"2023012810230735700_bts688-B36","doi-asserted-by":"crossref","DOI":"10.1109\/ICDM.2009.141","article-title":"A fully automated method for discovering community structures in high dimensional data","author":"Ruan","year":"2009"},{"key":"2023012810230735700_bts688-B37","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/msb4100129","article-title":"Network-based prediction of protein function","volume":"3","author":"Sharan","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023012810230735700_bts688-B38","doi-asserted-by":"crossref","first-page":"D698","DOI":"10.1093\/nar\/gkq1116","article-title":"The BioGRID interaction database: 2011 update","volume":"39","author":"Stark","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023012810230735700_bts688-B39","doi-asserted-by":"crossref","first-page":"1465","DOI":"10.1126\/science.1153878","article-title":"An in vivo map of the yeast protein interactome","volume":"320","author":"Tarassov","year":"2008","journal-title":"Science"},{"key":"2023012810230735700_bts688-B40","doi-asserted-by":"crossref","DOI":"10.1109\/ICDM.2006.70","article-title":"Fast random walk with restart and its applications","author":"Tong","year":"2006"},{"key":"2023012810230735700_bts688-B41","doi-asserted-by":"crossref","first-page":"1158","DOI":"10.1093\/bioinformatics\/btp118","article-title":"Identifying functional modules using expression profiles and confidence-scored protein interactions","volume":"25","author":"Ulitsky","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012810230735700_bts688-B42","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1186\/1471-2105-10-99","article-title":"Markov clustering versus affinity propagation for the partitioning of protein interaction graphs","volume":"10","author":"Vlasblom","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012810230735700_bts688-B43","doi-asserted-by":"crossref","first-page":"R271","DOI":"10.1186\/gb-2007-8-12-r271","article-title":"Consistent dissection of the protein interaction network by combining global and local metrics","volume":"8","author":"Wang","year":"2007","journal-title":"Genome Biol."},{"key":"2023012810230735700_bts688-B44","doi-asserted-by":"crossref","first-page":"1274","DOI":"10.1093\/bioinformatics\/btm087","article-title":"A new method to measure the semantic similarity of go terms","volume":"23","author":"Wang","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012810230735700_bts688-B45","first-page":"S10","article-title":"Recent advances in clustering methods for protein interaction networks","volume":"11","author":"Wang","year":"2010","journal-title":"BMC Genomics"},{"key":"2023012810230735700_bts688-B46","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1186\/1752-0509-4-36","article-title":"Building and analyzing protein interactome networks by cross-species comparisons","volume":"4","author":"Wiles","year":"2010","journal-title":"BMC Syst. Biol."},{"key":"2023012810230735700_bts688-B47","doi-asserted-by":"crossref","first-page":"976","DOI":"10.1093\/bioinformatics\/btq064","article-title":"Gosemsim: an R package for measuring semantic similarity among go terms and gene products","volume":"26","author":"Yu","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012810230735700_bts688-B48","doi-asserted-by":"crossref","first-page":"e59","DOI":"10.1371\/journal.pcbi.0030059","article-title":"The importance of bottlenecks in protein networks: correlation with gene essentiality and expression dynamics","volume":"3","author":"Yu","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023012810230735700_bts688-B49","doi-asserted-by":"crossref","first-page":"1158684","DOI":"10.1126\/science.1158684","article-title":"High-quality binary protein interaction map of the yeast interactome network","volume":"322","author":"Yu","year":"2008","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/3\/355\/48898127\/bioinformatics_29_3_355.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/3\/355\/48898127\/bioinformatics_29_3_355.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T11:51:37Z","timestamp":1674906697000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/3\/355\/257152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,11]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts688","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,2,1]]},"published":{"date-parts":[[2012,12,11]]}}}