title: PLW: Probabilistic Local Walks for detecting protein complexes from protein interaction networks.
abstract: BACKGROUND
  Many biological processes are carried out by proteins interacting with each other in the form of protein complexes. However, large-scale detection of protein complexes has remained constrained by experimental limitations. As such, computational detection of protein complexes by applying clustering algorithms on the abundantly available protein-protein interaction (PPI) networks is an important alternative. However, many current algorithms have overlooked the importance of selecting seeds for expansion into clusters without excluding important proteins and including many noisy ones, while ensuring a high degree of functional homogeneity amongst the proteins detected for the complexes.
  
  
  RESULTS
  We designed a novel method called Probabilistic Local Walks (PLW) which clusters regions in a PPI network with high functional similarity to find protein complex cores with high precision and efficiency in O (|V| log |V| + |E|) time. A seed selection strategy, which prioritises seeds with dense neighbourhoods, was devised. We defined a topological measure, called common neighbour similarity, to estimate the functional similarity of two proteins given the number of their common neighbours.
  
  
  CONCLUSIONS
  Our proposed PLW algorithm achieved the highest F-measure (recall and precision) when compared to 11 state-of-the-art methods on yeast protein interaction data, with an improvement of 16.7% over the next highest score. Our experiments also demonstrated that our seed selection strategy is able to increase algorithm precision when applied to three previous protein complex mining techniques.
  
  
  BACKGROUND
  The software, datasets and predicted complexes are available at http://wonglkd.github.io/PLW.
authors.forename: Daniel
authors.initials: D
authors.lastname: Wong
authors.forename: Xiao-Li
authors.initials: XL
authors.lastname: Li
authors.forename: Min
authors.initials: M
authors.lastname: Wu
authors.forename: Jie
authors.initials: J
authors.lastname: Zheng
authors.forename: See-Kiong
authors.initials: SK
authors.lastname: Ng
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D005656:Fungal Proteins / Q000032:analysis*; D025941:Protein Interaction Mapping; D012984:Software; D015003:Yeasts / Q000378:metabolism*
chemical_list: D005656:Fungal Proteins