An algorithm for identifying protein complexes based on clique percolation and distance restriction

Liu Bin-bin, LI Min, WANG Jian-xin, DUAN Gui-hua

Systems Engineering - Theory & Practice ›› 2012, Vol. 32 ›› Issue (2) : 390-397.

PDF(1154 KB)
中国科学院数学与系统科学研究院期刊网
PDF(1154 KB)
Systems Engineering - Theory & Practice ›› 2012, Vol. 32 ›› Issue (2) : 390-397. DOI: 10.12011/1000-6788(2012)2-390

An algorithm for identifying protein complexes based on clique percolation and distance restriction

  • Liu Bin-bin, LI Min, WANG Jian-xin, DUAN Gui-hua
Author information +
History +

Abstract

Identi cation of protein complexes in large interaction networks is crucial to understand prin-ciples of cellular organization and predict protein functions, which is one of the most important issues in the post-genomic era. Each protein might subordinate multiple protein complexes in the real protein-protein interaction networks. Identifying overlapping protein complexes from protein-protein interaction networks is a considerable research topic. As an e ective algorithm on identifying overlapping module structures, clique percolation method (CPM) has a wide range of application in social networks and bi-ological networks. However, CPM algorithm is recognition accuracy rate lowly and un t to identifying protein complexes with middling scale when it applied in PPI networks. In this paper, an algorithm called CPM-DR for identifying protein complexes based on clique percolation and distance restriction is pro-posed. In this algorithm, the scale of protein complex is restricted by distance constraint to conquest the drawbacks in CPM. The experiment results show that CPM-DR algorithm can identify many well known protein complexes more e ectively, precisely and comprehensively.

Key words

protein-protein interaction network / protein complexes / clique percolation / distance constraint

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
Liu Bin-bin, LI Min, WANG Jian-xin, DUAN Gui-hua. An algorithm for identifying protein complexes based on clique percolation and distance restriction. Systems Engineering - Theory & Practice, 2012, 32(2): 390-397 https://doi.org/10.12011/1000-6788(2012)2-390

References

[1] Garrels J I. Yeast genomic databases and the challenge of the post-genomic era[J]. Funct Integr Genomics, 2002, 2(4/5): 212-237.

[2] King A D, Przulj N, Jurisica I. Protein complex prediction via cost-based clustering[J]. Bioinformatics, 2004, 20: 3013-3020.

[3] Hartuv E, Shamir R. A clustering algorithm based graph connectivity[J]. Information Processing Letters, 2000, 76: 175-181.

[4] Girvan M, Newman M E J. Community structure in social and biological networks[J]. PNAS, 2002, 99: 7821-7826.

[5] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Phys Rev E, 2004, 69(6): 066133.

[6] Radicchi F, Castellano C, Cecconi F. De ning and identifying communities in networks[J]. Proc Natl Acad Sci USA, 2004, 101(9): 2658-2663.

[7] Luo F, Yang Y, Chen C F, et al. Modular organization of protein interaction networks[J]. Bioinformatics, 2007, 23(2): 207-214.

[8] Gregory S. An algorithm to nd overlapping community structure in networks[C]// Proc 11th European Con-ference on Principles and Practice of Knowledge Discovery in Databases (PKDD07), 2007: 91-102.

[9] Pinney J W,Westhead D R. Betweenness-Based Decomposition Methods for Social and Biological Networks[M]//BaxterS P, Mardia K, Walls R. Interdisciplinary Statistics and Bioinformatics, Leeds University Press, 2007: 87-90.

[10] Zhang S, Wang R S, Zhang X S. Identi cation of overlapping community structure in complex networks using fuzzy C-means clustering[J]. Physica A, 2007, 374: 483-490.

[11] Li M, Wang J X, Chen J E. A graph-theoretic method for mining overlapping functional modules in protein interaction networks[C]// Proceedings of the 4th International Symposium on Bioinformatics Research and Ap-plications, LNBI, 2008, 4983: 208-219.

[12] Palla G, Dernyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.

[13] Cho Y R, Hwang W, Ramanmathan M, et al. Semantic integration to identify overlapping functional modules in protein interaction networks[J]. BMC Bioinformatics, 2007, 8: 265.

[14] Altaf-UI-Amin M, Shinbo Y, Mihara K J, et al. Development and implementation of an algorithm for detection of protein complexes in large interaction networks[J]. BMC Bioinformatics, 2006, 7: 207.

[15] Li M, Chen J E, Wang J X, et al. Modifying the DPClus algorithm for identifying protein complexes based on new topological structures[J]. BMC Bioinformatics, 2008, 9: 398.

[16] Bader G D, Hogue C W. An automated method for nding molecular complexes in large protein interaction networks[J]. BMC Bioinformatics, 2003, 4: 2.

[17] Zhang S, Ning X, Zhang X S. Identi cation of functional modules in a PPI network by clique percolation clustering[J]. Comput Biol Chem, 2006, 30(6): 445-451.

[18] Jonsson P, Cavanna T, Zicha D, et al. Cluster analysis of networks generated through homology: Automatic identi cation of important protein communities involved in cancer metastatis[J]. BMC Bioinformatics, 2006, 7: 2.
PDF(1154 KB)

295

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉