Protein complex prediction for large protein protein interaction networks with the Core&Peel method

BMC Bioinformatics

Research

Miriam Baglioni¹  Filippo Geraci¹  Marco Pellegrini¹ 

[1] Laboratory for Integrative Systems Medicine - Istituto di Informatica e Telematica and Istituto di Fisiologia Clinica del CNR, via Moruzzi 1, 56124, Pisa, Italy;

关键词: Large PPI networks;    Protein complex prediction;    Efficient algorithm;   

DOI  :  10.1186/s12859-016-1191-6

来源: Springer

【 摘 要 】

BackgroundBiological 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.Results and discussionWe 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.ConclusionsOur 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.

【 授权许可】

CC BY   
© The Author(s) 2016

【 图 表 】

12864_2016_3098_Article_IEq78.gif

12877_2015_20_Article_IEq1.gif

12864_2017_4131_Article_IEq1.gif

12864_2015_2213_Article_IEq1.gif

12864_2017_4359_Article_IEq9.gif

12864_2016_3440_Article_IEq72.gif

12864_2017_3676_Article_IEq2.gif

12864_2017_3920_Article_IEq7.gif

12864_2017_4359_Article_IEq5.gif

12864_2015_2129_Article_IEq31.gif

12864_2016_3194_Article_IEq3.gif

12864_2016_2580_Article_IEq3.gif