Nucleic Acids Research, 2000, Vol. 28, No. 20 4029-4036
© 2000 Oxford University Press
Automatic detection of conserved gene clusters in multiple genomes by graph comparison and P-quasi grouping
Institute for Chemical Research, Kyoto University, Uji, Kyoto 611-0011, Japan and 1Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531, Japan
We previously reported two graph algorithms for analysis of genomic information: a graph comparison algorithm to detect locally similar regions called correlated clusters and an algorithm to find a graph feature called P-quasi complete linkage. Based on these algorithms we have developed an automatic procedure to detect conserved gene clusters and align orthologous gene orders in multiple genomes. In the first step, the graph comparison is applied to pairwise genome comparisons, where the genome is considered as a one-dimensionally connected graph with genes as its nodes, and correlated clusters of genes that share sequence similarities are identified. In the next step, the P-quasi complete linkage analysis is applied to grouping of related clusters and conserved gene clusters in multiple genomes are identified. In the last step, orthologous relations of genes are established among each conserved cluster. We analyzed 17 completely sequenced microbial genomes and obtained 2313 clusters when the completeness parameter P was 40%. About one quarter contained at least two genes that appeared in the metabolic and regulatory pathways in the KEGG database. This collection of conserved gene clusters is used to refine and augment ortholog group tables in KEGG and also to define ortholog identifiers as an extension of EC numbers.
* 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: Wataru Fujibuchi, National Center for Biotechnology Information, National Institutes of Health, Building 38A, Room B2N14, Bethesda, MD 20894, USA Hiroyuki Ogata, Information Génétique et Structurale, CNRS-UMR 1889, 31 Chemin Joseph Aiguier, 13402 Marseille Cedex 20, France
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  N. Sato Gclust: trans-kingdom classification of proteins using automatic individual threshold setting Bioinformatics, March 1, 2009; 25(5): 599 - 605. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Dessimoz, B. Boeckmann, A. C. J. Roth, and G. H. Gonnet Detecting non-orthology in the COGs database and other approaches grouping orthologs using genome-specific best hits Nucleic Acids Res., July 11, 2006; 34(11): 3309 - 3316. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. Pevzner and G. Tesler Genome Rearrangements in Mammalian Evolution: Lessons From Human and Mouse Genomes Genome Res., January 1, 2003; 13(1): 37 - 45. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. B. Rogozin, K. S. Makarova, J. Murvai, E. Czabarka, Y. I. Wolf, R. L. Tatusov, L. A. Szekely, and E. V. Koonin Connected gene neighborhoods in prokaryotic genomes Nucleic Acids Res., May 15, 2002; 30(10): 2212 - 2223. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Ogata, W. Fujibuchi, S. Goto, and M. Kanehisa A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters Nucleic Acids Res., October 15, 2000; 28(20): 4021 - 4028. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. I. Wolf, I. B. Rogozin, A. S. Kondrashov, and E. V. Koonin Genome Alignment, Evolution of Prokaryotic Genome Organization, and Prediction of Gene Function Using Genomic Context Genome Res., March 1, 2001; 11(3): 356 - 372. [Abstract] [Full Text]
|
|