A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters.

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.

Automatic detection of conserved gene clusters in multiple genomes by graph comparison and P-quasi grouping.

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.

PROSPECT improves cis-acting regulatory element prediction by integrating expression profile data with consensus pattern searches.

Consensus pattern and matrix-based searches designed to predict cis-acting transcriptional regulatory sequences have historically been subject to large numbers of false positives. We sought to decrease false positives by incorporating expression profile data into a consensus pattern-based search method. We have systematically analyzed the expression phenotypes of over 6000 yeast genes, across 121 expression profile experiments, and correlated them with the distribution of 14 known regulatory elements over sequences upstream of the genes. Our method is based on a metric we term probabilistic element assessment (PEA), which is a ranking of potential sites based on sequence similarity in the upstream regions of genes with similar expression phenotypes. For eight of the 14 known elements that we examined, our method had a much higher selectivity than a naïve consensus pattern search. Based on our analysis, we have developed a web-based tool called PROSPECT, which allows consensus pattern-based searching of gene clusters obtained from microarray data.

Prediction of gene expression specificity by promoter sequence patterns.

We present here a heuristic method toward predicting the expression specificity in the transcriptional process, which is known to be regulated in large part by promoter sequences, by observing the appearance of conserved sequence patterns in a group of known promoters, such as for housekeeping or tissue-specific genes. Statistically conserved patterns were automatically extracted from a set of unaligned sequences up to 200 bp upstream of the transcription initiation site, by a standard procedure using the Markov chain and binomial distribution models. Furthermore, to obtain signal sequences of optimal lengths we devised a method that combines the multiple alignment and the analysis of the information content (or relative entropy). Groups of related promoters were compiled from the EPD eukaryotic promoter database and the EMBL nucleic acid sequence database. Each promoter was examined for its specificity by linear discriminant analysis to test the validity of the extracted patterns. Our method could correctly discriminate 77.6% of the housekeeping gene promoters and 62.9% of the liver promoters.

The size differences among mammalian introns are due to the accumulation of small deletions.

In order to investigate the molecular mechanisms that alter intron size, we conducted an extensive interspecies comparison of homologous introns among three mammalian groups: human, artiodactyls, and rodents. The size differences of introns were statistically significant among all three groups (longest intron was for human and shortest for rodents), and appear to be due to the accumulation of small deletions, according to the separate count of insertion and deletion frequencies. The distribution of intron size differences also has a shape similar to that for the distribution of insertion/deletion sizes found in pseudogenes. It is suggested that introns are selectively neutral to small-scale changes of the genome size, which inherently contain the bias of favoring short deletions against short insertions.

Computation with the KEGG pathway database.

We introduce and discuss a new computational approach towards prediction and inference of biological functions from genomic sequences by making use of the pathway data in KEGG. Due to its piecewise nature, the current approach of predicting each gene function based on sequence similarity searches often fails to reconstruct cellular functions with all necessary components. The pathway diagram in KEGG, which may be considered a wiring diagram of molecules in biological systems, can be utilised as a reference for functional reconstruction. KEGG also contains binary relations that represent molecular interactions and relations and that can be utilised for computing and comparing pathways.

Splice variants in apoptotic pathway.

Elimination of superfluous or mutated somatic cells is provided by various mechanisms including apoptosis, and deregulation of apoptotic signaling pathways contributes to oncogenesis. 40 years have passed since the term "apoptosis" was introduced by Kerr et al. in 1972; among the programmed cell death, a variety of therapeutic strategies especially targeting apoptotic pathways have been investigated. Alternative precursor messenger RNA splicing, by which the process the exons of pre-mRNA are spliced in different arrangements to produce structurally and functionally distinct mRNA and proteins, is another field in progress, and it has been recognized as one of the most important mechanisms that maintains genomic and functional diversity. A variety of apoptotic genes are regulated through alternative pre-mRNA splicing as well, some of which have important functions as pro-apoptotic and anti-apoptotic factors. In this article we summarized splice variants of some of the apoptotic genes including BCL2L1, BIRC5, CFLAR, and MADD, as well as the regulatory mechanisms of alternative splicing of these genes. If the information of the apoptosis and aberrant splicing in each of malignancies is integrated, it will become possible to target proper variants for apoptosis, and the trans-elements themselves can become specific targets of cancer therapy as well. This article is part of a Special Issue entitled "Apoptosis: Four Decades Later".

Organizing and computing metabolic pathway data in terms of binary relations.

A new database system named KEGG is being organised to computerize functional aspects of genes and genomes in terms of the binary relations of interacting molecules or genes. We are currently working on the metabolic pathway database that is composed of three interconnected sections: genes, molecules, and pathways, which are also linked to a number of existing databases through our DBGET retrieval system. Here we present the basic concept of binary relations and hierarchical classifications to represent the metabolic pathway data. The database operations are then defined as an extension of the relational operations, and the path computation problem is considered as a deduction from binary relations. An example of using KEGG for the functional prediction of genomic sequences is presented.

KEGG: Kyoto Encyclopedia of Genes and Genomes.

Kyoto Encyclopedia of Genes and Genomes (KEGG) is a knowledge base for systematic analysis of gene functions in terms of the networks of genes and molecules. The major component of KEGG is the PATHWAY database that consists of graphical diagrams of biochemical pathways including most of the known metabolic pathways and some of the known regulatory pathways. The pathway information is also represented by the ortholog group tables summarizing orthologous and paralogous gene groups among different organisms. KEGG maintains the GENES database for the gene catalogs of all organisms with complete genomes and selected organisms with partial genomes, which are continuously re-annotated, as well as the LIGAND database for chemical compounds and enzymes. Each gene catalog is associated with the graphical genome map for chromosomal locations that is represented by Java applet. In addition to the data collection efforts, KEGG develops and provides various computational tools, such as for reconstructing biochemical pathways from the complete genome sequence and for predicting gene regulatory networks from the gene expression profiles. The KEGG databases are daily updated and made freely available (http://www.genome.ad.jp/kegg/).

DBGET/LinkDB: an integrated database retrieval system.

The integrated database retrieval system DBGET/LinkDB is the backbone of the Japanese GenomeNet service. DBGET is used to search and extract entries from a wide range of molecular biology databases, while LinkDB is used to search and compute links between entries in different databases. DBGET/LinkDB is designed to be a network distributed database system with an open architecture, which is suitable for incorporating local databases or establishing a specialized server environment. It also has an advantage of simple architecture allowing rapid daily updates of all the major databases. The WWW version of DBGET/LinkDB at GenomeNet is integrated with other search tools, such as BLAST, FASTA and MOTIF, and with local helper applications, such as RasMol. In addition to factual links between database entries, LinkDB is being extended to included similarity links and biological links toward computerization of logical reasoning processes.

Systematic Prediction of Orthologous Units of Genes in the Complete Genomes.

In order to fully make use of the vast amount of information in the complete genome sequences, we are developing a genome-scale system for predicting gene functions and cellular functions. The system makes use of the information of sequence similarity, the information of positional correlations in the genome, and the reference knowledge stored as the ortholog group tables in KEGG (Kyoto Encyclopedia of Genes and Genomes). The ortholog group table summarizes orthologous and paralogous relations among different organisms for a set of genes that are considered to form a functional unit, such as a conserved portion of the metabolic pathway or a molecular machinery for the membrane transport. At the moment, the ortholog group table is constructed for the cases where the genes are clustered in physically close positions in the genome for at least one organism. In this paper, we describe the system and the actual analysis of the complete genome of Pyrococcus horikoshii to identify ABC transporters.