|
|
A fast iterative-clique percolation method for
identifying functional modules in protein intreaction networks |
Penggang SUN , Lin GAO , |
School of Computer
Science and Technology, Xidian University, Xi’an 710071, China; |
|
|
Abstract Accumulating evidence suggests that biological systems are composed of interacting, separable, functional modules—groups of vertices within which connections are dense but between which they are sparse. Identifying these modules is likely through capturing the biologically meaningful interactions. In recent years, many algorithms have been developed for detecting such structures. These algorithms, however, are computationally demanding, which limits their applications. In this paper, we propose a fast iterative-clique percolation method (ICPM) for identifying overlapping functional modules in protein-protein interaction (PPI) networks. Our method is based on clique percolation method (CPM), and it not only considers the degree of nodes to minimize the search space (the vertices in k-cliques must have the degree of k
|
Keywords
iterative-clique percolation method (ICPM)
clique percolation method (CPM)
functional modules
protein-protein interaction (PPI)
|
Issue Date: 05 September 2009
|
|
|
Barabasi A, Oltvai Z. Network biology: understandingthe cell’s functional organization. Nature Reviews Genetics, 2004, 5(2): 101―113
doi: 10.1038/nrg1272
|
|
Spirin V, Mirny L. Protein complexes and functionalmodules in molecular networks. In: Proceedingsof the National Academy of Sciences, 2003, 100(21): 12123―12126
doi: 10.1073/pnas.2032324100
|
|
Gao L, Sun P G, Song J. Clustering Algorithms for detecting functional modulesin protein interaction networks. Journalof Bioinformatics and Computational Biology, 2009, 7(1): 217―242
doi: 10.1142/S0219720009004023
|
|
Bader G D, Hogue C W. An automated method for findingmolecular complexes in large protein interaction networks. BMC Bioinformatics, 2003, 4(2): 1―17
|
|
King A, Przulj N, Jurisica I. Protein complex prediction via cost-based clustering. Bioinformatics, 2004, 20(17): 3013―3020
doi: 10.1093/bioinformatics/bth351
|
|
Přzulj N. Wigle D, Jurisica I. Functional topology in a network of protein interactions. Bioinformatics, 2004, 20(3): 340―348
doi: 10.1093/bioinformatics/btg415
|
|
Dongen S V. Graph clustering by flow simulation. PhD thesis centers for mathematicsand computer science (CWI). Utrecht:University of Utrecht, 2000
|
|
Enright A J, Dongen S V, Ouzounis C A. An efficient algorithm for large-scale detection of proteinfamilies. Nucleic Acids Research, 2002, 30(7): 1575―1584
doi: 10.1093/nar/30.7.1575
|
|
Brohee S. Helden J. Evaluation of clusteringalgorithms for proteinprotein interaction networks. BMC Bioinformatics, 2006, 7(488): 1―19
|
|
Blatt M, Wiseman S, Domany E. Superparamagnetic clustering of data. Physical Review Letters, 1996, 76(18): 3251―3254
doi: 10.1103/PhysRevLett.76.3251
|
|
Palla G. Uncoveringthe overlapping community structure of complex networks in natureand society. Nature, 2005, 435(7043): 814―818
doi: 10.1038/nature03607
|
|
Zhang S H, Ning X M, Zhang X S. Identification of functional modules in a PPI networkby clique percolation clustering. ComputationalBiology and Chemistry, 2006, 30(6): 445―451
doi: 10.1016/j.compbiolchem.2006.10.001
|
|
Ruepp A. TheFunCat, a functional annotation scheme for systematic classificationof proteins from whole genomes. NucleicAcids Research, 2004, 32(18): 5539―5545
doi: 10.1093/nar/gkh894
|
|
Bu D. Topologicalstructure analysis of the protein–protein interaction networkin budding yeast. Nucleic Acids Research, 2003, 31(9): 2443―2450
doi: 10.1093/nar/gkg340
|
|
Sharan R. Conservedpatterns of protein interaction in multiple species. In: Proceedings of the National Academy of Sciences, 2005, 102(6): 1974―1979
doi: 10.1073/pnas.0409522102
|
|
Goldberg D S. Assessing experimentally derived interactions in a small world. In: Proceedings of the National Academy of Sciences, 2003, 100(8): 4372―4376
doi: 10.1073/pnas.0735871100
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|