Weighted Clustering Coefficient for Identifying Modular Formations in Protein-Protein Interaction Networks

Authors: Zelmina Lubovac, Björn Olsson, Jonas Gamalielsson

Abstract:

This paper describes a novel approach for deriving modules from protein-protein interaction networks, which combines functional information with topological properties of the network. This approach is based on weighted clustering coefficient, which uses weights representing the functional similarities between the proteins. These weights are calculated according to the semantic similarity between the proteins, which is based on their Gene Ontology terms. We recently proposed an algorithm for identification of functional modules, called SWEMODE (Semantic WEights for MODule Elucidation), that identifies dense sub-graphs containing functionally similar proteins. The rational underlying this approach is that each module can be reduced to a set of triangles (protein triplets connected to each other). Here, we propose considering semantic similarity weights of all triangle-forming edges between proteins. We also apply varying semantic similarity thresholds between neighbours of each node that are not neighbours to each other (and hereby do not form a triangle), to derive new potential triangles to include in module-defining procedure. The results show an improvement of pure topological approach, in terms of number of predicted modules that match known complexes.

Keywords: Modules, systems biology, protein interactionnetworks, yeast.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078313

References:

[1] L. H. Hartwell, J. J. Hopfield, S. Leibler, and A. W. Murray, "From molecular to modular cell biology," Nature, vol. 402, pp. C47-52, 1999.
[2] V. Spirin and L. A. Mirny, "Protein complexes and functional modules in molecular networks," Proc Natl Acad Sci U S A, vol. 100, pp. 12123- 8, 2003.
[3] D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks," Nature, vol. 393, pp. 440-2, 1998.
[4] Z. Lubovac, J. Gamalielsson, and B. Olsson, "Combining functional and topological properties to identify core modules in protein interaction networks," Proteins, 2006.
[5] A. W. Rives and T. Galitski, "Modular organization of cellular networks," Proc Natl Acad Sci U S A, vol. 100, pp. 1128-33, 2003.
[6] J. B. Pereira-Leal, A. J. Enright, and C. A. Ouzounis, "Detection of functional modules from protein interaction networks," Proteins, vol. 54, pp. 49-57, 2004.
[7] J. F. Poyatos and L. D. Hurst, "How biologically relevant are interaction-based modules in protein networks?," Genome Biol, vol. 5, pp. R93, 2004.
[8] G. D. Bader and C. W. Hogue, "An automated method for finding molecular complexes in large protein interaction networks," BMC Bioinformatics, vol. 4, pp. 2, 2003.
[9] N. Speer, H. Fröhlich, C. Spieth, and A. Zell, "Functional Grouping of Genes Using Spectral Clustering and Gene Ontology," presented at IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB 2005), San Diego, USA, 2005.
[10] J.-P. Onella, J. Saram├ñki, J. Kertész, and K. Kaski, "Intensity and coherence of motifs in weighted complex networks," Physical Reviews E, vol. 71, pp. 065103, 2005.
[11] A. H. Tong, B. Drees, G. Nardelli, G. D. Bader, B. Brannetti, L. Castagnoli, M. Evangelista, S. Ferracuti, B. Nelson, S. Paoluzi, M. Quondam, A. Zucconi, C. W. Hogue, S. Fields, C. Boone, and G. Cesareni, "A combined experimental and computational strategy to define protein interaction networks for peptide recognition modules," Science, vol. 295, pp. 321-4, 2002.
[12] S. Wuchty and E. Almaas, "Peeling the yeast protein network," Proteomics, vol. 5, pp. 444-9, 2005.
[13] I. Xenarios, D. W. Rice, L. Salwinski, M. K. Baron, E. M. Marcotte, and D. Eisenberg, "DIP: the database of interacting proteins," Nucleic Acids Res, vol. 28, pp. 289-91, 2000.
[14] T. Ito, T. Chiba, R. Ozawa, M. Yoshida, M. Hattori, and Y. Sakaki, "A comprehensive two-hybrid analysis to explore the yeast protein interactome," Proc Natl Acad Sci U S A, vol. 98, pp. 4569-74, 2001.
[15] "Creating the gene ontology resource: design and implementation," Genome Res, vol. 11, pp. 1425-33, 2001.
[16] M. Deng, Z. Tu, F. Sun, and T. Chen, "Mapping Gene Ontology to proteins based on protein-protein interaction data," Bioinformatics, vol. 20, pp. 895-902, 2004.
[17] U. Karaoz, T. M. Murali, S. Letovsky, Y. Zheng, C. Ding, C. R. Cantor, and S. Kasif, "Whole-genome annotation by using evidence integration in functional-linkage networks," Proc Natl Acad Sci U S A, vol. 101, pp. 2888-93, 2004.
[18] D. Lin, "An information-theoretic definition of similarity," presented at The 15th International Conference on Mashine Learning, Madison, WI, 1998.
[19] S. S. Dwight, M. A. Harris, K. Dolinski, C. A. Ball, G. Binkley, K. R. Christie, D. G. Fisk, L. Issel-Tarver, M. Schroeder, G. Sherlock, A. Sethuraman, S. Weng, D. Botstein, and J. M. Cherry, "Saccharomyces Genome Database (SGD) provides secondary gene annotation using the Gene Ontology (GO)," Nucleic Acids Res, vol. 30, pp. 69-72, 2002.
[20] J. J. Jiang and D. W. Conrath, "Semantic similarity based on corpus statistics and lexical taxonomy," presented at International Conference on Research in Computational Linguistics, Taiwan, 1998.
[21] P. Resnik, "Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language," Journal of Artificial Intelligence Research, vol. 11, pp. 95- 130, 1999.
[22] P. W. Lord, R. D. Stevens, A. Brass, and C. A. Goble, "Investigating semantic similarity measures across the Gene Ontology: the relationship between sequence and annotation," Bioinformatics, vol. 19, pp. 1275-83, 2003.
[23] A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani, "The architecture of complex weighted networks," Proc Natl Acad Sci U S A, vol. 101, pp. 3747-52, 2004.
[24] E. Bouveret, G. Rigaut, A. Shevchenko, M. Wilm, and B. Seraphin, "A Sm-like protein complex that participates in mRNA degradation," Embo J, vol. 19, pp. 1661-71, 2000.
[25] W. He and R. Parker, "Functions of Lsm proteins in mRNA degradation and splicing," Curr Opin Cell Biol, vol. 12, pp. 346-50, 2000.
[26] S. Tharun, W. He, A. E. Mayes, P. Lennertz, J. D. Beggs, and R. Parker, "Yeast Sm-like proteins function in mRNA decapping and decay," Nature, vol. 404, pp. 515-8, 2000.
[27] R. Knauer and L. Lehle, "The oligosaccharyltransferase complex from Saccharomyces cerevisiae. Isolation of the OST6 gene, its synthetic interaction with OST3, and analysis of the native complex," J Biol Chem, vol. 274, pp. 17249-56, 1999.