Nucleic Acids Research, 2000, Vol. 28, No. 20 4021-4028
© 2000 Oxford University Press
A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters
Institute for Chemical Research, Kyoto University, Uji, Kyoto 611-0011, Japan
The availability of computerized knowledge on biochemical pathways in the KEGG database opens new opportunities for developing computational methods to characterize and understand higher level functions of complete genomes. Our approach is based on the concept of graphs; for example, the genome is a graph with genes as nodes and the pathway is another graph with gene products as nodes. We have developed a simple method for graph comparison to identify local similarities, termed correlated clusters, between two graphs, which allows gaps and mismatches of nodes and edges and is especially suitable for detecting biological features. The method was applied to a comparison of the complete genomes of 10 microorganisms and the KEGG metabolic pathways, which revealed, not surprisingly, a tendency for formation of correlated clusters called FRECs (functionally related enzyme clusters). However, this tendency varied considerably depending on the organism. The relative number of enzymes in FRECs was close to 50% for Bacillus subtilis and Escherichia coli, but was <10% for Synechocystis and Saccharomyces cerevisiae. The FRECs collection is reorganized into a collection of ortholog group tables in KEGG, which represents conserved pathway motifs with the information about gene clusters in all the completely sequenced genomes.
* To whom correspondence should be addressed. Tel: +81 774 38 3270; Fax: +81 774 38 3269; Email: kanehisa@kuicr.kyoto-u.ac.jp Present addresses: Hiroyuki Ogata, Information Génétique et Structurale, CNRS-UMR 1889, 31 Chemin Joseph Aiguier, 13402 Marseille Cedex 20, France Wataru Fujibuchi, National Center for Biotechnology Information, National Institutes of Health, Building 38A, Room B2N14, Bethesda, MD 20894, USA
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. L. Menon, F. L. Poole II, A. Cvetkovic, S. A. Trauger, E. Kalisiak, J. W. Scott, S. Shanmukh, J. Praissman, F. E. Jenney Jr., W. R. Wikoff, et al. Novel Multiprotein Complexes Identified in the Hyperthermophilic Archaeon Pyrococcus furiosus by Non-denaturing Fractionation of the Native Proteome Mol. Cell. Proteomics, April 1, 2009; 8(4): 735 - 751. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 L. Chen, L. Zhang, Y. Zhao, L. Xu, Y. Shang, Q. Wang, W. Li, H. Wang, and X. Li Prioritizing risk pathways: a novel association approach to searching for disease pathways fusing SNPs and pathways Bioinformatics, January 15, 2009; 25(2): 237 - 242. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 B. S. Srinivasan, N. H. Shah, J. A. Flannick, E. Abeliuk, A. F. Novak, and S. Batzoglou Current progress in network research: toward reference networks for key model organisms Brief Bioinform, September 1, 2007; 8(5): 318 - 332. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Z. Li, S. Zhang, Y. Wang, X.-S. Zhang, and L. Chen Alignment of molecular networks by integer quadratic programming Bioinformatics, July 1, 2007; 23(13): 1631 - 1639. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 N. H. Bergman, K. D. Passalacqua, P. C. Hanna, and Z. S. Qin Operon Prediction for Sequenced Bacterial Genomes without Experimental Information Appl. Envir. Microbiol., February 1, 2007; 73(3): 846 - 854. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. Flannick, A. Novak, B. S. Srinivasan, H. H. McAdams, and S. Batzoglou Graemlin: General and robust alignment of multiple large interaction networks Genome Res., September 1, 2006; 16(9): 1169 - 1181. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 V. Spirin, M. S. Gelfand, A. A. Mironov, and L. A. Mirny A metabolic network in the evolutionary context: Multiscale structure and modularity PNAS, June 6, 2006; 103(23): 8774 - 8779. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Okuda, T. Katayama, S. Kawashima, S. Goto, and M. Kanehisa ODB: a database of operons accumulating known operons across multiple genomes Nucleic Acids Res., January 1, 2006; 34(suppl_1): D358 - D362. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. Boyer, A. Morgat, L. Labarre, J. Pothier, and A. Viari Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data Bioinformatics, December 1, 2005; 21(23): 4209 - 4215. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Y. Pinter, O. Rokhlenko, E. Yeger-Lotem, and M. Ziv-Ukelson Alignment of metabolic pathways Bioinformatics, August 15, 2005; 21(16): 3401 - 3408. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Cabusora, E. Sutton, A. Fulmer, and C. V. Forst Differential network expression during drug and stress response Bioinformatics, June 15, 2005; 21(12): 2898 - 2905. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Pasek, A. Bergeron, J.-L. Risler, A. Louis, E. Ollivier, and M. Raffinot Identification of genomic features using microsyntenies of domains: Domain teams Genome Res., June 1, 2005; 15(6): 867 - 874. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Sharan, S. Suthram, R. M. Kelley, T. Kuhn, S. McCuine, P. Uetz, T. Sittler, R. M. Karp, and T. Ideker From the Cover: Conserved patterns of protein interaction in multiple species PNAS, February 8, 2005; 102(6): 1974 - 1979. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. P. Kelley, B. Yuan, F. Lewitter, R. Sharan, B. R. Stockwell, and T. Ideker PathBLAST: a tool for alignment of protein interaction networks Nucleic Acids Res., July 1, 2004; 32(suppl_2): W83 - W88. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. P. Kelley, R. Sharan, R. M. Karp, T. Sittler, D. E. Root, B. R. Stockwell, and T. Ideker Conserved pathways within bacteria and yeast as revealed by global protein network alignment PNAS, September 30, 2003; 100(20): 11394 - 11399. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. Zheng, J. D. Szustakowski, L. Fortnow, R. J. Roberts, and S. Kasif Computational Identification of Operons in Microbial Genomes Genome Res., August 1, 2002; 12(8): 1221 - 1230. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Kanehisa, S. Goto, S. Kawashima, and A. Nakaya The KEGG databases at GenomeNet Nucleic Acids Res., January 1, 2002; 30(1): 42 - 46. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. Ogata, S. Audic, P. Renesto-Audiffren, P.-E. Fournier, V. Barbe, D. Samson, V. Roux, P. Cossart, J. Weissenbach, J.-M. Claverie, et al. Mechanisms of Evolution in Rickettsia conorii and R. prowazekii Science, September 14, 2001; 293(5537): 2093 - 2098. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. Fujibuchi, H. Ogata, H. Matsuda, and M. Kanehisa Automatic detection of conserved gene clusters in multiple genomes by graph comparison and P-quasi grouping Nucleic Acids Res., October 15, 2000; 28(20): 4029 - 4036. [Abstract] [Full Text] [PDF]
|
|