Weighted Clustering Coefficient for Identifying Modular Formations in Protein-Protein Interaction Networks
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:61022", author = "Zelmina Lubovac and Björn Olsson and Jonas Gamalielsson", title = "Weighted Clustering Coefficient for Identifying Modular Formations in Protein-Protein Interaction Networks", 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.", volume = "2", number = "2", pages = "552-6", }
