Automatic Detection of Gene Clusters
by P-Quasi Complete Linkage Grouping

Wataru Fujibuchi 1

Hiroyuki Ogata 1

wataru@kuicr.kyoto-u.ac.jp

ogata@kuicr.kyoto-u.ac.jp

matsuda@ics.es.osaka-u.ac.jp

kanehisa@kuicr.kyoto-u.ac.jp

Hideo Matsuda 2

1
2Minoru Kanehisa 1

Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011,
Japan
Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan

1 Introduction
It is known that bacteria genomes are highly organized to express functions cooperatively, for instance,by operons or by locating related genes adjacently on the genome for the transcriptional advantage.
Since the complete sequences of several genomes were released, the gene clusters that are de ned
as locally conserved gene sets beyond species have been progressively studied for these few years[1, 2, 3, 5]. However, it seems dicult to extract functionally important gene clusters manually
because the detecting of gene clusters depends on which organisms to compare. Our goal is to extract
signi cant gene clusters automatically with appropriate level of conservation among various species.
In our system, tentatively called P-quasi completeness gene cluster detector, or P-CGC detector, themagnitude of signi cance of gene clusters can be controlled by P-% completeness of linkage of geneclusters, in other words, by the extent of conservation among various species.

2 Method and System
We use 14 microorganisms and the whole processes to detect gene clusters are as follows:
1. Best hit search with Smith-Waterman score equal to or more than 100
2. Extraction of possible gene clusters by SIMIC search, allowing insertion,deletion and permutationof genes
3. P-quasi complete linkage grouping of gene clusters among 14 species
4. Identi cation of orthologs and paralogs by COG+ method where paralogous genes are added toCOGs [4]3 Results and Discussions
We examined a various set of parameter values, P, and obtained the range of 20{60% that best
extracted signi cant gene clusters. Fig. 1 is an example of extracted gene clusters (P=20%). The
ATPase cluster seems to entirely reproduce the manual version of KEGG database. In addition,
several interesting characteristics are found in the cluster. Generally speaking, archaeal ATPases
contain common subunits, chain (cog1), (cog3), B (cog5) and C (cog6) as eubacteria, but they haveunique subunits that are di erent from eubacteria (cog9{12 that apparently substitute for cog0, cog2,300

Figure 1: ATPase cluster: table and wired image of orthologs.
cog4, cog7). Moreover, there are duplicated homologs for B chain (cog5). However, it is interesting tond that only B. burgdorferi (bbu) has unique archaeal characteristics among eubacteria. Furthermore,in A. aeolicus (aae), the cluster is divided into four or more pieces on the genome.
We think that our system can correctly detect appropriate gene clusters automatically and weare now improving and extending it for representing paralogous genes and fusion genes eciently.
Through this work, we expect to analyze the statistical di erences of genome organization amongorganisms and it would provide us with the understanding of the history of genome evolution.

Acknowledgements
This work was supported in part by a Grant-in-Aid for Scienti c Research on Priority Areas, `GenomeScience', from the Ministry of Education, Science, Sports and Culture of Japan. The computation time
was provided by the Supercomputer Laboratory, Institute for Chemical Research, Kyoto University.

References[1] Mushegian, A.R. and Koonin, E.V., Gene order is not conserved in bacterial evolution, Trends
Genet., 12:289{230, 1997.
[2] Siefert, J.L., Martin, K.A., Abdi, F., Widger, W.R. and Fox, G.E., Conserved gene clusters inbacterial genomes provide further support for the primacy of RNA, J. Mol. Evol., 45:467{472,1997.
[3] Tatusov, R.L., Mushegian, A.R., Bork, P., Brown, N.P., Hayes, W.S., Borodovsky, M, Rudd,K.E. and Koonin, E.V., Metabolism and evolution of Haemophilus in uenzae deduced from awhole-genome comparison with Escherichia coli, Curr. Biol., 6:279{291, 1996.
[4] Tatusov, R.L., Koonin, E.V. and Lipman, D.J., A genomic perspective on protein families, Science, 278:631-637, 1997.
[5] Watanabe, H., Mori, H., Itoh, T. and Gojobori, T., Genome plasticity as a paradigm of eubacteria
evolution, J. Mol. Evol., 44(Supple 1):S57{S64, 1997.
301