title: A novel link prediction algorithm for reconstructing protein-protein interaction networks by topological similarity.
abstract: BACKGROUND
  Recent advances in technology have dramatically increased the availability of protein-protein 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.
  
  
  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%.
  
  
  BACKGROUND
  www.cs.utsa.edu/∼jruan/RWS/.
authors.affiliation: Department of Computer Science, The University of Texas at San Antonio, San Antonio, TX 78249, USA.
authors.forename: Chengwei
authors.initials: C
authors.lastname: Lei
authors.forename: Jianhua
authors.initials: J
authors.lastname: Ruan
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D006801:Humans; D046912:Multiprotein Complexes / Q000378:metabolism; D025941:Protein Interaction Mapping / Q000379:methods*; D060066:Protein Interaction Maps; D029701:Saccharomyces cerevisiae Proteins / Q000378:metabolism
chemical_list: D046912:Multiprotein Complexes; D029701:Saccharomyces cerevisiae Proteins