title: Protein complex prediction for large protein protein interaction networks with the Core&Peel method.
abstract: BACKGROUND
  Biological networks play an increasingly important role in the exploration of functional modularity and cellular organization at a systemic level. Quite often the first tools used to analyze these networks are clustering algorithms. We concentrate here on the specific task of predicting protein complexes (PC) in large protein-protein interaction networks (PPIN). Currently, many state-of-the-art algorithms work well for networks of small or moderate size. However, their performance on much larger networks, which are becoming increasingly common in modern proteome-wise studies, needs to be re-assessed.
  
  
  CONCLUSIONS
  We present a new fast algorithm for clustering large sparse networks: Core&Peel, which runs essentially in time and storage O(a(G)m+n) for a network G of n nodes and m arcs, where a(G) is the arboricity of G (which is roughly proportional to the maximum average degree of any induced subgraph in G). We evaluated Core&Peel on five PPI networks of large size and one of medium size from both yeast and homo sapiens, comparing its performance against those of ten state-of-the-art methods. We demonstrate that Core&Peel consistently outperforms the ten competitors in its ability to identify known protein complexes and in the functional coherence of its predictions. Our method is remarkably robust, being quite insensible to the injection of random interactions. Core&Peel is also empirically efficient attaining the second best running time over large networks among the tested algorithms.
  
  
  CONCLUSIONS
  Our algorithm Core&Peel pushes forward the state-of the-art in PPIN clustering providing an algorithmic solution with polynomial running time that attains experimentally demonstrable good output quality and speed on challenging large real networks.
authors.affiliation: Laboratory for Integrative Systems Medicine - Istituto di Informatica e Telematica and Istituto di Fisiologia Clinica del CNR, via Moruzzi 1, Pisa, 56124, Italy. m.pellegrini@iit.cnr.it.
authors.forename: Marco
authors.initials: M
authors.lastname: Pellegrini
authors.affiliation: Laboratory for Integrative Systems Medicine - Istituto di Informatica e Telematica and Istituto di Fisiologia Clinica del CNR, via Moruzzi 1, Pisa, 56124, Italy.
authors.forename: Miriam
authors.initials: M
authors.lastname: Baglioni
authors.affiliation: Laboratory for Integrative Systems Medicine - Istituto di Informatica e Telematica and Istituto di Fisiologia Clinica del CNR, via Moruzzi 1, Pisa, 56124, Italy.
authors.forename: Filippo
authors.initials: F
authors.lastname: Geraci
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D006801:Humans; D011485:Protein Binding; D025941:Protein Interaction Mapping / Q000379:methods*; D060066:Protein Interaction Maps; D011506:Proteins / Q000378:metabolism*; D020543:Proteome / Q000378:metabolism; D012441:Saccharomyces cerevisiae / Q000235:genetics / Q000378:metabolism*
chemical_list: D011506:Proteins; D020543:Proteome
keywords: Efficient algorithm; Large PPI networks; Protein complex prediction