Skip Navigation

This Article
Right arrow Full Text Freely available
Right arrow Print PDF (343K) Freely available
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (49)
Right arrowRequest Permissions
Right arrow Commercial Re-use Guidelines
for Open Access NAR Content
Google Scholar
Right arrow Articles by Ogata, H.
Right arrow Articles by Kanehisa, M.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Ogata, H.
Right arrow Articles by Kanehisa, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

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

Hiroyuki Ogata, Wataru Fujibuchi, Susumu Goto and Minoru Kanehisa*

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


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Nucleic Acids ResHome page
C. Li, X. Li, Y. Miao, Q. Wang, W. Jiang, C. Xu, J. Li, J. Han, F. Zhang, B. Gong, et al.
SubpathwayMiner: a software package for flexible identification of pathways
Nucleic Acids Res., October 1, 2009; 37(19): e131 - e131.
[Abstract] [Full Text] [PDF]

Home page
 Mol. Cell. ProteomicsHome page
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]

Home page
 BioinformaticsHome page
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]

Home page
 Brief BioinformHome page
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]

Home page
 BioinformaticsHome page
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]

Home page
 Appl. Environ. Microbiol.Home page
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]

Home page
 Genome ResHome page
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]

Home page
 Proc. Natl. Acad. Sci. USAHome page
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]

Home page
 Nucleic Acids ResHome page
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]

Home page
 BioinformaticsHome page
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]

Home page
 BioinformaticsHome page
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]

Home page
 BioinformaticsHome page
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]

Home page
 Genome ResHome page
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]

Home page
 Proc. Natl. Acad. Sci. USAHome page
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]

Home page
 Nucleic Acids ResHome page
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]

Home page
 Proc. Natl. Acad. Sci. USAHome page
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]

Home page
 Genome ResHome page
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]

Home page
 Nucleic Acids ResHome page
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]

Home page
 ScienceHome page
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]

Home page
 Nucleic Acids ResHome page
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]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.