Abstract
Protein-protein interaction networks serve to carry out basic molecular activity in the cell. Detecting the modular structures from the protein-protein interaction network is important for understanding the organization, function and dynamics of a biological system. In order to identify functional neighborhoods based on network topology, many network cluster identification algorithms have been developed. However, each algorithm might dissect a network from a different aspect and may provide different insight on the network partition. In order to objectively evaluate the performance of four commonly used cluster detection algorithms: molecular complex detection (MCODE), NetworkBlast, shortest-distance clustering (SDC) and Girvan-Newman (G-N) algorithm, we compared the biological coherence of the network clusters found by these algorithms through a uniform evaluation framework. Each algorithm was utilized to find network clusters in two different protein-protein interaction networks with various parameters. Comparison of the resulting network clusters indicates that clusters found by MCODE and SDC are of higher biological coherence than those by NetworkBlast and G-N algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Hartwell L H, Hopfield J J, Leibler S, et al. From molecular to modular cell biology. Nature, 1999, 402: 47–52
Gavin A C, Bosche M, Krause R, et al. Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature, 2002, 415: 141–147
Giot L, Bader J S, Brouwer C, et al. A protein interaction map of Drosophila melanogaster. Science, 2003, 302: 1727–1736
Ho Y, Gruhler A, Heilbut A, et al. Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry. Nature, 2002, 415: 180–183
Ito T, Chiba T, Ozawa R, et al. A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc Natl Acad Sci USA, 2001, 98: 4569–4574
Li S, Armstrong C M, Bertin N, et al. A map of the interactome network of the metazoan C. elegans. Science, 2004, 303: 540–543
Rual J F, Venkatesan K, Hao T, et al. Towards a proteome-scale map of the human protein-protein interaction network. Nature, 2005, 437: 1173–1178
Stelzl U, Worm U, Lalowski M, et al. A human protein-protein interaction network: A resource for annotating the proteome. Cell, 2005, 122: 957–968
Uetz P, Giot L, Cagney G, et al. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae. Nature, 2000, 403: 623–627
Barabasi A L, Oltvai Z N. Network biology: Understanding the cell’s functional organization. Nat Rev Genet, 2004, 5: 101–113
Ravasz E, Barabasi A L. Hierarchical organization in complex networks. Phys Rev E Stat Nonlin Soft Matter Phys, 2003, 67: 026112
Rives A W, Galitski T. Modular organization of cellular networks. Proc Natl Acad Sci USA, 2003, 100: 1128–1133
Spirin V, Mirny L. A Protein complexes and functional modules in molecular networks. Proc Natl Acad Sci USA, 2003, 100: 12123–12128
Brohee S, van Helden J. Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics, 2006, 7: 488
Mewes H W, Frishman D, Guldener U, et al. MIPS: a database for genomes and protein sequences. Nucleic Acids Res, 2002, 30: 31–34
Bader G D, Hogue C W. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 2003, 4: 2
Sharan R, Suthram S, Kelley R M, et al. Conserved patterns of protein interaction in multiple species. Proc Natl Acad Sci USA, 2005, 102: 1974–1979
Girvan M, Newman M E. Community structure in social and biological networks. Proc Natl Acad Sci USA, 2002, 99: 7821–7826
Newman M E, Girvan M. Finding and evaluating community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys, 2004, 69: 026113
von Mering C, Krause R, Snel B, et al. Comparative assessment of large-scale data sets of protein-protein interactions. Nature, 2002, 417: 399–403
Han J D, Dupuy D, Bertin N, et al. Effect of sampling on topology predictions of protein-protein interaction networks. Nat Biotechnol, 2005, 23: 839–844
Xenarios I, Salwinski L, Duan X J, et al. DIP, the Database of Interacting Proteins: A research tool for studying cellular networks of protein interactions. Nucleic Acids Res, 2002, 30: 303–305
Peri S, Navarro J D, Amanchy R, et al. Development of human protein reference database as an initial platform for approaching systems biology in humans. Genome Res, 2003, 13: 2363–2371
Deane C M, Salwinski L, Xenarios I, et al. Protein interactions: Two methods for assessment of the reliability of high throughput observations. Mol Cell Proteomics, 2002, 1: 349–356
Ashburner M, Ball C A, Blake J A, et al. Gene ontology: Tool for the unification of biology. The Gene Ontology Consortium. Nat Genet, 2000, 25: 25–29
Han J D, Bertin N, Hao T, et al. Evidence for dynamically organized modularity in the yeast protein-protein interaction network. Nature, 2004, 430: 88–93
Snel B, Bork P, Huynen M A. The identification of functional modules from the genomic association of genes. Proc Natl Acad Sci USA, 2002, 99: 5890–5895
Mahadevan R, Palsson B O Properties of metabolic networks: Structure versus function. Biophys J, 2005, 88: L07–09
Holme P, Huss M, Jeong H. Subnetwork hierarchies of biochemical pathways. Bioinformatics, 2003, 19: 532–538
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the National Natural Science Foundation of China (Grant No. 30588001)
About this article
Cite this article
Dong, D., Zhou, B. & Han, JD.J. Comparing the biological coherence of network clusters identified by different detection algorithms. CHINESE SCI BULL 52, 2938–2944 (2007). https://doi.org/10.1007/s11434-007-0454-z
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s11434-007-0454-z