![[Feedback]](/icons/banner/feedbackACT.gif){kind=icon}
![[For Subscribers]](/icons/banner/subscriberACT.gif){kind=icon}
![[Archive]](/icons/banner/archiveACT.gif){kind=icon}
![[Search]](/icons/banner/searchACT.gif){kind=icon}
![[Contents]](/icons/banner/tocACT.gif){kind=icon}
|
|
|
|
|
||
|
METHODS Informatics for Unveiling Hidden Genome Signatures1Division of Evolutionary Genetics, Department of Population Genetics, National Institute of Genetics, The Graduate University for Advanced Studies, Mishima, Shizuoka-ken 411-8540, Japan;2 Xanagen Inc., Sakado, Takatsu-ku, Kawasaki, Kanagawa-ken 213-0012, Japan; 3ACT-JST (Applying Advanced Computational Science and Technology, Japan Science and Technology Corp.), Kawaguchi, Saitama-ken, 332-0012, Japan; 4Department of Bioinformatics and Genomes, Graduate School of Information Science, Nara Institute of Science and Technology, Takayama, Ikoma, Nara-ken 630-0101, Japan; 5CREST JST (Core Research for Evolutional Science and Technology, Japan Science and Technology Corp.), Kawaguchi, Saitama-ken, 332-0012, Japan; 6Department of Bio-System Engineering, Faculty of Engineering, Yamagata University, Yonezawa, Yamagata-ken 992-8510, Japan
With the increasing amount of available genome sequences, novel tools are needed for comprehensive analysis of species-specific sequence characteristics for a wide variety of genomes. We used an unsupervised neural network algorithm, a self-organizing map (SOM), to analyze di-, tri-, and tetranucleotide frequencies in a wide variety of prokaryotic and eukaryotic genomes. The SOM, which can cluster complex data efficiently, was shown to be an excellent tool for analyzing global characteristics of genome sequences and for revealing key combinations of oligonucleotides representing individual genomes. From analysis of 1- and 10-kb genomic sequences derived from 65 bacteria (a total of 170 Mb) and from 6 eukaryotes (460 Mb), clear species-specific separations of major portions of the sequences were obtained with the di-, tri-, and tetranucleotide SOMs. The unsupervised algorithm could recognize, in most 10-kb sequences, the species-specific characteristics (key combinations of oligonucleotide frequencies) that are signature features of each genome. We were able to classify DNA sequences within one and between many species into subgroups that corresponded generally to biological categories. Because the classification power is very high, the SOM is an efficient and fundamental bioinformatic strategy for extracting a wide range of genomic information from a vast amount of sequences. [Supplemental material is available online at www.genome.org.]
In addition to protein-coding information, genome sequences contain a wealth of information of interest in many fields of biology, from molecular evolution to genome engineering. G+C% has been used as a fundamental characteristic of individual genomes, but the G+C% is apparently too simple a parameter to differentiate a wide variety of genomes of known sequences. Oligonucleotide frequency can be used to distinguish genomes, because oligonucleotide frequencies vary significantly among genomes; dinucleotide frequencies, for example, are shown to be genome signatures for both prokaryotes and eukaryotes (Nussinov 1984  ; Karlin et al. 1997; Karlin 1998; Gentles and Karlin
2001). Comprehensive analyses of oligonucleotide frequencies in a wide
variety of genomes are thought to provide fundamental knowledge of
individual genomes, namely, key combinations of oligonucleotides
responsible for the biological properties of the different genomes and
genome portions. We applied Kohonen's self-organizing map (SOM) to
create graphical representations of oligonucleotide frequencies from
which we could extract a wide range of genomic information. The
unsupervised neural network algorithm is an effective tool for
clustering and visualizing high-dimensional data; it converts complex
nonlinear relations among high-dimensional data into simple geometric
relations that can be viewed in two dimensions (Kohonen 1982, 1990;
Kohonen et al. 1996).
We and others have used SOMs to characterize codon usage patterns of a
wide variety of bacteria (Kanaya et al. 1998
Species-Specific Oligonucleotide Frequencies in Bacterial Genomes SOMs were constructed with di-, tri-, and tetranucleotide frequencies for  17,000 genomic 10-kb sequences derived from the 65
bacterial genomes whose complete sequences are known. As the first step
to obtaining the initial weight vectors, frequencies for the 17,000
non-overlapping segments were analyzed by principal component analysis
(PCA). This is based on the knowledge that multivariate analyses
including PCA successfully classified gene sequences into groups
corresponding to known biological categories when the numbers of
sequences and species were much smaller than that analyzed here
(Grantham et al. 1980; Medigue et al. 1991; Sharp and Matassi 1994;
Andersson and Sharp 1996). After 40 learning cycles, oligonucleotide
frequencies of genome sequences were effectively reflected as the
weight vectors in SOMs (Fig. 1A–C).
Comparison of the sequence classification into lattice points of the
final weight vectors with that of the initial vectors set by the first
and second principal components of PCA (Fig. 1G) showed that sequences
of a single species were much more tightly clustered in the final
vectors. Lattices that include sequences from a single species are
indicated in color, and those including sequences of more than one
species are indicated in black. In the SOMs, sequences of most species
were separated into species-specific nonoverlapping zones (Fig. 1A–C).
In contrast, the resolving power of the conventional PCA method that
was estimated with the initial vectors (Fig. 1G) was poor. The
contiguous nonintermingling zones that contained sequences of a single
species were very limited when compared with the contiguous
nonoverlapping zones obtained with SOMs.
Analysis of the weight vectors for individual lattices showed that strongly biased vectors were localized to the edge of the map, whereas those with weakly biased vectors were in the center. The G+C% for each weight vector in di-, tri-, and tetranucleotide SOMs (abbreviated as di-, tri-, and tetra-SOMs) was reflected mainly in the horizontal axis and increased from left to right; sequences of AT- and GC-rich bacteria were distributed on the left and right sides of the SOMs, respectively (Fig. 1D–F). Importantly, sequences with the same G+C% are separated by a complex combination of oligonucleotide frequencies resulting in species-specific separations. In other words, most of the 10-kb segments in each genome have a combination of oligonucleotides that reflect the respective genome like a signature, and SOMs can reveal the signature as representative weight vectors. The 170,000 nonoverlapping 1-kb sequences were also analyzed (Fig. 2). Species-specific separations were again observed, although the resolution was somewhat reduced. This shows that species-specific signatures are detectable even in a major population of the 1-kb sequences.
Intraspecies Separation for Bacterial Genomes Detailed inspection of SOMs showed that each species was often split into two major zones that were composed of roughly equal numbers of data points. To illustrate this split more clearly, data points for each of seven representative species in the 10-kb tri-SOM (Fig. 1B) and in the 1-kb tri- and tetra-SOMs (Fig. 2B,C) were plotted with a single color (Fig. 3A–C). In the 1-kb SOMs, intraspecies separations were observed for all seven species, but in the 10-kb SOM, the separation was not observed for three species. To investigate the biological significance of the two zones, correlation with transcription polarities of protein coding sequences (CDSs) in the respective genomic segments was examined for Escherichia coli and Bacillus subtilis from CDSs data compiled in the DDBJ Genome Information Broker (http://gib.genes.nig.ac.jp/). Sequences belonging to each major zone in the 1-kb tetra-SOMs (Fig. 3C) are illustrated separately as red and blue bands below the diagrams that show transcription polarities of CDSs in the 200-kb segment (Fig. 3D,E). A red or blue band in each species showed clustering of contiguous 1-kb sequences belonging to one of the two zones in the 1-kb SOM. Each band coincided with the clustering of CDSs with one polarity, and borders between red and blue bands were usually located at positions corresponding to the switch positions for transcription polarity. In the cases of the three species for which the intraspecies separation was lost in the 10-kb SOM, switching of transcriptional polarities occurs within a 10-kb segment at higher probabilities than observed for the other four species (data not shown). These findings indicate that codon usage patterns contribute to the intraspecies separations and probably also to the interspecies separations.
Genome segments introduced through horizontal transfer from distantly related organisms are known to retain the sequence characteristics of the donor genome and can be distinguished from those of the acceptor genome (Lawrence and Ochman 1997 , 1998). For example, genes transferred
from other genomes often have codon-usage patterns distinct from those
of their intrinsic genomes (Grantham et al. 1980; Ikemura 1985; Medigue
et al. 1991). We showed previously that SOMs are useful for identifying
horizontally transferred genes and, importantly, for predicting the
donor genomes of the transferred genes (Kanaya et al. 2001). There are
characteristic data points in Figure 3A that are located away from the
major zones of individual species. Those sequences that have
oligonucleotide frequencies clearly distinct from those of major zones
should correspond, at least in part, to genome portions that have been
transferred horizontally from other genomes. To test this possibility,
we examined 10-kb sequences from E. coli that were located
outside of the territories of both E. coli and a closely
related bacterium Salmonella typhimurium. When the sequences
in the S. typhimurium territory were excluded, the next
highest number of E. coli sequences was found in the
Yersinia pestis territory. We then focused the five sequences
in the Y. pestis territory commonly found in the di-, tri-,
and tetra-SOMs. Within these sequences, there were 37 known genes, 23
of which had significant homology with Y. pestis genes. For
example, at the amino acid level, 6 of 23 proteins had identity levels
greater than 60%, and the highest was 80%, which was significantly
higher than the 40% calculated for the average identity for the
orthogonal pairs of E. coli and Y. pestis proteins
(Deng et al. 2002). Furthermore, three genes were homologous with the
phage-encoded genes, and one was homologous with a transposon gene.
These findings support the prediction that these genes may have been
transferred horizontally into the E. coli genome from other
organisms.
SOMs for Eukaryotic Genomes
The G+C% calculated for each weight vector in di-, tri-, and tetra-SOMs are shown in Figure 4, D–F. It is apparent that sequences with the same G+C% are separated by a complex combination of oligonucleotide frequencies resulting in species-specific separations. Underlying representation in SOMs enables us to retrieve characteristic sequence patterns for individual genomes and genome regions. The frequency of each dinucleotide in the weight vector for each lattice in the di-SOM is illustrated in red and blue (Fig. 5). Complementary pairs of dinucleotides (e.g., AA vs. TT) had similar distribution patterns. This indicates that when the sequence complementary to the sequence registered by the International DNA Databank is used for a certain genome, general patterns may not change appreciably. Lines in all panels in Figure 5 represent the species borders observed in the di-SOM. Species borders coincide with regions of transition between the red and blue levels for several dinucleotides, which correspond to the diagnostic dinucleotides for the species border formation. For example, the CG dinucleotide deficiency (dark blue zones in the CG panel) is a factor responsible for separation of human sequences (red in Fig. 4A) from Drosophila (pink) and Arabidopsis (green) sequences. Levels of CG, GC, AG, and GA contributed appreciably to separation of Drosophila sequences from others. It should be stressed that the SOM utilizes complex combinations of many more dinucleotides for the sequence separations in an area-dependent manner. This is because SOMs implement nonlinear projection from the multi-dimensional space of input data onto a two-dimensional array of weight vectors (Kohonen 1982 , 1990; Kohonen et al. 1996).
In similar fashion, trinucleotide levels for each representative vector in the tri-SOM were analyzed. Again, species borders often coincided with regions of sharp transition between the red and blue levels for various diagnostic trinucleotides (Fig. 6). For humans, high levels of AGG, CAG, CCC, CCT, CTG, and GGG as well as low levels of ACG, CGA, CGT, and TCG were observed, and for Drosophila, high levels of GCA and TGC and low levels of AGA, GCC, TCA, TCT, and TGA were observed. The under-representation of CNG in a major portion of the Arabidopsis territory is thought to be related to cytosine methylation in CNG trinucleotides (Lindroth et al. 2001 ). The SOM utilizes complex combinations of many trinucleotides
for species separation in an area-dependent manner; the 64 panels for
all trinucleotides are presented as supplementary data 1.
Intraspecies Separation Observed for Eukaryote Genomes Human sequences had two and one satellite zones in the di- and tri-SOMs, respectively (red minor zones in Fig. 4A,B). Genomes of warm-blooded vertebrates, such as humans, are known to be composed of long-range segmental G+C% distributions isochores (Bernardi et al. 1985 ; Ikemura and Aota 1988; Bernardi 1989; Gautier 2000; Eyre-Walker
and Hurst 2001). Correlation of the segmental G+C% distributions with
SOM separations was observed. For example, 500 10-kb sequences
belonging to the satellite red zone located at top at the left side in
the di- and tri-SOMs were practically common between the two SOMs, and
the G+C% was between 30% and 33%, which corresponds to very AT-rich
sequences in the human genome. Four-fifths of the sequences were
derived from very AT-rich gene-desert regions on chromosome 21 (Hattori
et al. 2000), which correspond to L1 isochores (Saccone et al. 1999)
and replicate very late during S phase (Watanabe et al. 2002). The SOM
can unveil specific genome portions with distinct characteristics as
intraspecies separations. Drosophila sequences were split into
two major zones in the tetra-SOM (pink in Fig. 4C), and this split was
associated with G+C%.
SOMs With 1-kb Eukaryote Sequences
It should be noted that many of the 1-kb segments are free of species-specific ubiquitous repetitive elements, such as Alu or L1 elements in the human genome. The sequences with or without repetitive elements were found to be colocalized in the major zones of individual species. Detailed inspection showed that 10-kb human sequences with or without Alu or L1 elements were also colocalized in the human major zones on the 10-kb SOMs. Therefore, the major factors responsible for the species-specific separations of eukaryote sequences do not appear to be ubiquitous repetitive elements. Factors responsible for the separations could be characteristics that are more extensively embedded than repetitive elements.
Biological Implications of SOM Separations and Genome Signatures To investigate the biological significance of diagnostic oligonucleotides for SOM separations, we examined the correlation of levels of palindromic tetranucleotides with respective restriction enzyme systems by referring to the restriction enzyme database (REBASE; http://vent.neb.com/ vincze/genomes/). Restriction site
tetranucleotides were under-represented in 10 of the 11 bacteria that
have genes encoding 4-base cutter enzymes (blue in Fig. 3F). This
finding is consistent with that of Karlin et al. (1997) on
compositional biases of bacterial genomes, again indicating that SOMs
can effectively classify sequences according to biological categories.
The 256 panels for all tetranucleotides in the prokaryote and eukaryote
SOMs are presented as supplementary data 2 and 3, respectively. We then
considered the biological significance of diagnostic tetranucleotides
in eukaryotes. One possible explanation is a contributory effect of
levels of the di- and trinucleotide components of tetranucleotides. For
example, tetranucleotides containing the CG dinucleotide were clearly
under-represented in the human territory (supplementary data 3).
Transition zones of various other tetranucleotides (e.g., CTCA and
CTGA) were also sharp and coincided exactly with species borders. Such
sharp transitions and exact coincidences were not typical for the
dinucleotide components (e.g., CT, TC, and CA in Fig. 5). As found in
the restriction enzyme analysis, some tetranucleotides may have
biological significance. Species-specific characteristics for DNA
synthesis and repair enzymes, as well as sequence preferences of
ubiquitous DNA-binding proteins, may be responsible for differences in
oligonucleotide distribution between species. In the cases of signal
and motif sequences, such as transcription factor-binding sites, they
may be biased from the random occurrence statistically calculated from
the genome base composition. This prediction is consistent with the
finding that GAGA/TCTC, which is a transcription signal in
Drosophila (Soeller et al. 1993), was under-represented in the
Drosophila genome (supplementary data 3). SOMs for longer
oligonucleotides such as penta- and hexanucleotides may reveal a wide
range of signal and motif sequences, because these sequences are
typically longer than tetranucleotides. A preliminary study of the
correlation of diagnostic oligonucleotide with sequence motifs for
transcription factors suggested that such sequences are often
under-represented in a major portion of the respective genome, and,
therefore, may contribute to genome signatures. Because
species-specific separations in SOMs are very clear, SOMs may provide
fundamental guidelines for identifying molecular mechanisms that
established genome signatures of individual species during evolution.
The present analysis is an example of comparative genomics, and the
results obtained were affected by choice of the genomes used. As a
strategy to reduce this effect, most (if not all) genomes that have
been sequenced completely were analyzed.
Genome Sequences The DNA sequences of 65 bacterial genomes, itemized in the Figure 1 legend, were obtained from the DDBJ GIB Web site (http://www.ddbj.nig.ac.jp/), and those of the 6 eukaryotes itemized in the Figure 4 legend were obtained from the GenBank Web site (http://www.ncbi.nlm.nih.gov/Genbank/).
Self-Organizing Map
In Step 3, the ijth weight vector was updated by
 (r)  i‘ i + (r) and
j – (r) j' j + (r). The two parameters  (r)
and (r) are learning coefficients for the rth cycle, and
Nij is the number of components of Sij. In the
present study, (r) and (r) are set by
(1) and (1) are the initial values for the T-cycle of
the learning process. In the present study, we selected 40 for T, 0.6
for (1), and 20 for (1). The learning process is monitored by the
total distance between xk, and the nearest weight
vector wI‘j‘, represented as
The SOM program used for the sequence analyses "XanaMine" was obtained from Xanagen Inc. (URL; http://www.xanagen.com/index-e.html, E-mail; info{at}xanagen.com).
http://gib.genes.nig.ac.jp/; DDBJ Genome Information Broker Web site.
http://vent.neb.com/ http://www.ddbj.nig.ac.jp/; DDBJ Web site. http://www.ncbi.nlm.nih.gov/Genbank/; GenBank Web site. http://www.xanagen.com/index-e.html; SOM programs for genome analysis.
This work was supported by ACT—Japan Science and Technology Corporation and by the Advanced and Innovational Research Program in Life Sciences and a Grant-in-Aid for Scientific Research on Priority Areas (C) "Genome Science" from the Ministry of Education, Culture, Sports, Science and Technology of Japan. We thank Ms. Nanayo Ishihara and Yoko Kosaka for technical assistance. The publication costs of this article were defrayed in part by payment of page charges. This article must therefore be hereby marked "advertisement" in accordance with 18 USC section 1734 solely to indicate this fact.
7 Corresponding author.  E-MAIL tikemura{at}lab.nig.ac.jp; FAX 81-55-981-6794. Article and publication are at http://www.genome.org/cgi/doi/10.1101/gr.634603.
Received July 16, 2002; accepted in revised format January 28, 2003. 13:693-702 © by 2003 Cold Spring Harbor Laboratory Press ISSN 1088-9051/03 $5.00  CiteULike  Connotea  Del.icio.us  Digg  Reddit  Technorati What's this?
This article has been cited by other articles:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Top
ABSTRACT
RESULTS
1) of the first
principal component; and the second dimension (J) was defined by the
nearest integer greater than 
