This paper presents an algorithm called DPClusO for partitioning simple graphs into overlapping modules, that is, clusters constrained by density and periphery tracking. The major advantages of DPClusO over the related and previously published algorithm DPClus are shorter running time and ensuring coverage, that is, each node goes to at least one module. DPClusO is a general-purpose clustering algorithm and useful for finding overlapping cohesive groups in a simple graph for any type of application. This work shows that the modules generated by DPClusO from several PPI networks of yeast with high-density constraint match with more known complexes compared to some other recently published complex generating algorithms. Furthermore, the biological significance of the high density modules has been demonstrated by comparing their P values in the context of Gene Ontology (GO) terms with those of the randomly generated modules having the same size, distribution, and zero density. As a consequence, it was also learnt that a PPI network is a combination of mainly high-density and star-like modules. 1. Introduction The ability to generate comprehensive datasets incorporating all biological molecules and their interactions at different omics levels has led to the emergence of system biology. Cellular functions rely on the coordinated actions of multiple genes, RNAs, proteins, and metabolites. Therefore, organizing biological information in the context of networks is important for holistic understanding of biological systems. Some characteristics of the biological networks are that they are complex, autonomous, robust, function to execute physicochemical processes, and are conserved but can adjust [1]. Constructing biological networks by integrating information piece by piece has led to the discovery of emergent topological properties in terms of degree distribution, average path length, clustering coefficient, robustness, and so forth. These emergent properties of biological networks are quite distinct compared to those of the randomized networks of the same size and could not be understood by analyzing an individual or a small group of components. On the other hand networks having the same global topological property for example, degree distributionn may have different local topologies [2]. Analyzing these local topologies is useful to understand the design principles of biological networks and the functions of the individual components. A feature for many networks including biological networks is their modular organization. Modularity is a property that allows
References
[1]
B. O. Palsson, Systems Biology: Properties of Reconstructed Networks, Cambridge University Press, Cambridge, UK, 2007.
[2]
J. D. J. Han, “Understanding biological functions through molecular networks,” Cell Research, vol. 18, no. 2, pp. 224–237, 2008.
[3]
L. H. Hartwell, J. J. Hopfield, S. Leibler, and A. W. Murray, “From molecular to modular cell biology,” Nature, vol. 402, no. 6761, pp. C47–C52, 1999.
[4]
N. Guelzim, S. Bottani, P. Bourgine, and F. Képès, “Topological and causal structure of the yeast transcriptional regulatory network,” Nature Genetics, vol. 31, no. 1, pp. 60–63, 2002.
[5]
E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A. L. Barabási, “Hierarchical organization of modularity in metabolic networks,” Science, vol. 297, no. 5586, pp. 1551–1555, 2002.
[6]
J. B. Pereira-Leal, A. J. Enright, and C. A. Ouzounis, “Detection of Functional Modules from Protein Interaction Networks,” Proteins: Structure, Function and Genetics, vol. 54, no. 1, pp. 49–57, 2004.
[7]
A. C. Gavin, P. Aloy, P. Grandi et al., “Proteome survey reveals modularity of the yeast cell machinery,” Nature, vol. 440, no. 7084, pp. 631–636, 2006.
[8]
B. A. Shoemaker and A. R. Panchenko, “Deciphering protein-protein interactions. Part I. Experimental techniques and databases,” PLoS Computational Biology, vol. 3, no. 3, article e42, pp. 0337–0344, 2007.
[9]
Y. Ho, A. Gruhler, A. Heilbut et al., “Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry,” Nature, vol. 415, no. 6868, pp. 180–183, 2002.
[10]
M. Arifuzzaman, M. Maeda, A. Itoh et al., “Large-scale identification of protein-protein interaction of Escherichia coli K-12,” Genome Research, vol. 16, no. 5, pp. 686–691, 2006.
[11]
B. Schwikowski, P. Uetz, and S. Fields, “A network of protein-protein interactions in yeast,” Nature Biotechnology, vol. 18, no. 12, pp. 1257–1261, 2000.
[12]
G. D. Bader and C. W. V. Hogue, “An automated method for finding molecular complexes in large protein interaction networks,” BMC Bioinformatics, vol. 4, article 2, 2003.
[13]
M. Wu, X. Li, C. K. Kwoh, and S. K. Ng, “A core-attachment based method to detect protein complexes in PPI networks,” BMC Bioinformatics, vol. 10, article 169, 2009.
[14]
H. C. M. Leung, Q. Xiang, S. M. Yiu, and F. Y. L. Chin, “Predicting protein complexes from PPI data: a core-attachment approach,” Journal of Computational Biology, vol. 16, no. 2, pp. 133–144, 2009.
[15]
S. Srihari, K. Ning, and H. W. Leong, “Refining Markov Clustering for protein complex prediction by incorporating core-attachment structure,” Genome Informatics, vol. 23, no. 1, pp. 159–168, 2009.
S. Pu, J. Wong, B. Turner, E. Cho, and S. J. Wodak, “Up-to-date catalogues of yeast protein complexes,” Nucleic Acids Research, vol. 37, no. 3, pp. 825–831, 2009.
[18]
J. D. Eblen, I. C. Gerling,, A. M. Saxton, J. Wu, J. R. Snoddy, and M. A. Langston, “Graph algorithms for integrated biological analysis, with application to type 1 diabetes data,” in Clustering Challenges in Biological Networks, S. Butenko, W. A. Chaovalitwongse, and P. M. Pardalos, Eds., pp. 207–222, World Scientific, 2009.
[19]
M. A. Langston, L. Lin, X. Peng, et al., “A combinatorial approach to the analysis of differential gene expression data: the use of graph algorithms for disease prediction and screening,” in Methods of Microarray Data Analysis IV, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2005.
[20]
E. Georgii, S. Dietmann, T. Uno, P. Pagel, and K. Tsuda, “Enumeration of condition-dependent dense modules in protein interaction networks,” Bioinformatics, vol. 25, no. 7, pp. 933–940, 2009.
[21]
M. Zhang, J. Deng, C. V. Fang, X. Zhang, and L. J. Lu, “Molecular network analysis and applications,” in Knowledge-Based Bioinformatics: From Analysis to Interpretation, G. Alterovitz and M. Romani, Eds., pp. 253–287, John Wiley & sons, New York, NY, USA, 2010.
[22]
M. Altaf-Ul-Amin, Y. Shinbo, K. Mihara, K. Kurokawa, and S. Kanaya, “Development and implementation of an algorithm for detection of protein complexes in large interaction networks,” BMC Bioinformatics, vol. 7, article 207, 2006.
[23]
M. Altaf-Ul-Amin, H. Tsuji, K. Kurokawa, et al., “A density-periphery based graph clustering software mainly focused on detection of protein complexes in interaction networks,” Journal of Computer Aided Chemistry, vol. 7, pp. 150–156, 2006.
[24]
N. J. Krogan, G. Cagney, H. Yu et al., “Global landscape of protein complexes in the yeast Saccharomyces cerevisiae,” Nature, vol. 440, no. 7084, pp. 637–643, 2006.
[25]
http://dip.mbi.ucla.edu/.
[26]
ftp://ftpmips.gsf.de/yeast/PPI/.
[27]
H. Jeong, S. P. Mason, A. L. Barabási, and Z. N. Oltvai, “Lethality and centrality in protein networks,” Nature, vol. 411, no. 6833, pp. 41–42, 2001.
[28]
http://geneontology.org/.
[29]
S. Falcon and R. Gentleman, “Using GOstats to test gene lists for GO term association,” Bioinformatics, vol. 23, no. 2, pp. 257–258, 2007.
