SUMMARY: KofamKOALA is a web server to assign KEGG Orthologs (KOs) to protein sequences by homology search against a database of profile hidden Markov models (KOfam) with pre-computed adaptive score thresholds. KofamKOALA is faster than existing KO assignment tools with its accuracy being comparable to the best performing tools. Function annotation by KofamKOALA helps linking genes to KEGG resources such as the KEGG pathway maps and facilitates molecular network reconstruction. AVAILABILITY AND IMPLEMENTATION: KofamKOALA, KofamScan and KOfam are freely available from GenomeNet (https://www.genome.jp/tools/kofamkoala/). SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: In contrast to the increasing number of the successful genome projects, there still remain many orphan metabolites for which their synthesis processes are unknown. Metabolites, including these orphan metabolites, can be classified into groups that share the same core substructures, originated from the same biosynthetic pathways. It is known that many metabolites are synthesized by adding up building blocks to existing metabolites. Therefore, it is proposed that, for any given group of metabolites, finding the core substructure and the branched substructures can help predict their biosynthetic pathway. There already have been many reports on the multiple graph alignment techniques to find the conserved chemical substructures in relatively small molecules. However, they are optimized for ligand binding and are not suitable for metabolomic studies. RESULTS: We developed an efficient multiple graph alignment method named as MUCHA (Multiple Chemical Alignment), specialized for finding metabolic building blocks. This method showed the strength in finding metabolic building blocks with preserving the relative positions among the substructures, which is not achieved by simply applying the frequent graph mining techniques. Compared with the combined pairwise alignments, this proposed MUCHA method generally reduced computational costs with improving the quality of the alignment. CONCLUSIONS: MUCHA successfully find building blocks of secondary metabolites, and has a potential to complement to other existing methods to reconstruct metabolic networks using reaction patterns.

MOTIVATION: In silico prediction of drug-target interactions from heterogeneous biological data is critical in the search for drugs and therapeutic targets for known diseases such as cancers. There is therefore a strong incentive to develop new methods capable of detecting these potential drug-target interactions efficiently. RESULTS: In this article, we investigate the relationship between the chemical space, the pharmacological space and the topology of drug-target interaction networks, and show that drug-target interactions are more correlated with pharmacological effect similarity than with chemical structure similarity. We then develop a new method to predict unknown drug-target interactions from chemical, genomic and pharmacological data on a large scale. The proposed method consists of two steps: (i) prediction of pharmacological effects from chemical structures of given compounds and (ii) inference of unknown drug-target interactions based on the pharmacological effect similarity in the framework of supervised bipartite graph inference. The originality of the proposed method lies in the prediction of potential pharmacological similarity for any drug candidate compounds and in the integration of chemical, genomic and pharmacological data in a unified framework. In the results, we make predictions for four classes of important drug-target interactions involving enzymes, ion channels, GPCRs and nuclear receptors. Our comprehensively predicted drug-target interaction networks enable us to suggest many potential drug-target interactions and to increase research productivity toward genomic drug discovery. SUPPLEMENTARY INFORMATION: Datasets and all prediction results are available at http://cbio.ensmp.fr/~yyamanishi/pharmaco/. AVAILABILITY: Softwares are available upon request.

MOTIVATION: The IUBMB's Enzyme Nomenclature system, commonly known as the Enzyme Commission (EC) numbers, plays key roles in classifying enzymatic reactions and in linking the enzyme genes or proteins to reactions in metabolic pathways. There are numerous reactions known to be present in various pathways but without any official EC numbers, most of which have no hope to be given ones because of the lack of the published articles on enzyme assays. RESULTS: In this article we propose a new method to predict the potential EC numbers to given reactant pairs (substrates and products) or uncharacterized reactions, and a web-server named E-zyme as an application. This technology is based on our original biochemical transformation pattern which we call an 'RDM pattern', and consists of three steps: (i) graph alignment of a query reactant pair (substrates and products) for computing the query RDM pattern, (ii) multi-layered partial template matching by comparing the query RDM pattern with template patterns related with known EC numbers and (iii) weighted major voting scheme for selecting appropriate EC numbers. As the result, cross-validation experiments show that the proposed method achieves both high coverage and high prediction accuracy at a practical level, and consistently outperforms the previous method. AVAILABILITY: The E-zyme system is available at http://www.genome.jp/tools/e-zyme/.

MOTIVATION: The identification of interactions between drugs and target proteins is a key area in genomic drug discovery. Therefore, there is a strong incentive to develop new methods capable of detecting these potential drug-target interactions efficiently. RESULTS: In this article, we characterize four classes of drug-target interaction networks in humans involving enzymes, ion channels, G-protein-coupled receptors (GPCRs) and nuclear receptors, and reveal significant correlations between drug structure similarity, target sequence similarity and the drug-target interaction network topology. We then develop new statistical methods to predict unknown drug-target interaction networks from chemical structure and genomic sequence information simultaneously on a large scale. The originality of the proposed method lies in the formalization of the drug-target interaction inference as a supervised learning problem for a bipartite graph, the lack of need for 3D structure information of the target proteins, and in the integration of chemical and genomic spaces into a unified space that we call 'pharmacological space'. In the results, we demonstrate the usefulness of our proposed method for the prediction of the four classes of drug-target interaction networks. Our comprehensively predicted drug-target interaction networks enable us to suggest many potential drug-target interactions and to increase research productivity toward genomic drug discovery. AVAILABILITY: Softwares are available upon request. SUPPLEMENTARY INFORMATION: Datasets and all prediction results are available at http://web.kuicr.kyoto-u.ac.jp/supp/yoshi/drugtarget/.

UNLABELLED: Infectious diseases are a major threat to global public health and prosperity. The causative agents consist of a suite of pathogens, ranging from bacteria to viruses, including fungi, helminthes and protozoa. Although these organisms are extremely varied in their biological structure and interactions with the host, they share similar methods of evading the host immune system. Antigenic variation and drift are mechanisms by which pathogens change their exposed epitopes while maintaining protein function. Accordingly, these traits enable pathogens to establish chronic infections in the host. The varDB database was developed to serve as a central repository of protein and nucleotide sequences as well as associated features (e.g. field isolate data, clinical parameters, etc.) involved in antigenic variation. The data currently contained in varDB were mined from GenBank as well as multiple specialized data repositories (e.g. PlasmoDB, GiardiaDB). Family members and ortholog groups were identified using a hierarchical search strategy, including literature/author-based searches and HMM profiles. Included in the current release are>29,00 sequences from 39 gene families from 25 different pathogens. This resource will enable researchers to compare antigenic variation within and across taxa with the goal of identifying common mechanisms of pathogenicity to assist in the fight against a range of devastating diseases. AVAILABILITY: varDB is freely accessible at http://www.vardb.org/

Mining frequent patterns from large datasets is an important issue in data mining. Recently, complex and unstructured (or semi-structured) datasets have appeared as targets for major data mining applications, including text mining, web mining and bioinformatics. Our work focuses on labeled ordered trees, which are typically semi-structured datasets. In bioinformatics, carbohydrate sugar chains, or glycans, can be modeled as labeled ordered trees. Glycans are the third major class of biomolecules, having important roles in signaling and recognition. For mining labeled ordered trees, we propose a new probabilistic model and its efficient learning scheme which significantly improves the time and space complexity of an existing probabilistic model for labeled ordered trees. We evaluated the performance of the proposed model, comparing it with those of other probabilistic models, using synthetic as well as real datasets from glycobiology. Experimental results showed that the proposed model drastically reduced the computation time of the competing model, keeping the predictive power and avoiding overfitting to the training data. Finally, we assessed our results on real data from a variety of biological viewpoints, verifying known facts in glycobiology.

MOTIVATION: Neurodegenerative disorders (NDDs) are progressive and fatal disorders, which are commonly characterized by the intracellular or extracellular presence of abnormal protein aggregates. The identification and verification of proteins interacting with causative gene products are effective ways to understand their physiological and pathological functions. The objective of this research is to better understand common molecular pathogenic mechanisms in NDDs by employing protein-protein interaction networks, the domain characteristics commonly identified in NDDs and correlation among NDDs based on domain information. RESULTS: By reviewing published literatures in PubMed, we created pathway maps in Kyoto Encyclopedia of Genes and Genomes (KEGG) for the protein-protein interactions in six NDDs: Alzheimer's disease (AD), Parkinson's disease (PD), amyotrophic lateral sclerosis (ALS), Huntington's disease (HD), dentatorubral-pallidoluysian atrophy (DRPLA) and prion disease (PRION). We also collected data on 201 interacting proteins and 13 compounds with 282 interactions from the literature. We found 19 proteins common to these six NDDs. These common proteins were mainly involved in the apoptosis and MAPK signaling pathways. We expanded the interaction network by adding protein interaction data from the Human Protein Reference Database and gene expression data from the Human Gene Expression Index Database. We then carried out domain analysis on the extended network and found the characteristic domains, such as 14-3-3 protein, phosphotyrosine interaction domain and caspase domain, for the common proteins. Moreover, we found a relatively high correlation between AD, PD, HD and PRION, but not ALS or DRPLA, in terms of the protein domain distributions. AVAILABILITY: http://www.genome.jp/kegg/pathway/hsa/hsa01510.html (KEGG pathway maps for NDDs).

BACKGROUND: Selenocysteine and pyrrolysine are the 21st and 22nd amino acids, which are genetically encoded by stop codons. Since a number of microbial genomes have been completely sequenced to date, it is tempting to ask whether the 23rd amino acid is left undiscovered in these genomes. Recently, a computational study addressed this question and reported that no tRNA gene for unknown amino acid was found in genome sequences available. However, performance of the tRNA prediction program on an unknown tRNA family, which may have atypical sequence and structure, is unclear, thereby rendering their result inconclusive. A protein-level study will provide independent insight into the novel amino acid. RESULTS: Assuming that the 23rd amino acid is also encoded by a stop codon, we systematically predicted proteins that contain stop-codon-encoded amino acids from 191 prokaryotic genomes. Since our prediction method relies only on the conservation patterns of primary sequences, it also provides an opportunity to search novel selenoproteins and other readthrough proteins. It successfully recovered many of currently known selenoproteins and pyrrolysine proteins. However, no promising candidate for the 23rd amino acid was detected, and only one novel selenoprotein was predicted. CONCLUSION: Our result suggests that the unknown amino acid encoded by stop codons does not exist, or its phylogenetic distribution is rather limited, which is in agreement with the previous study on tRNA. The method described here can be used in future studies to explore novel readthrough events from complete genomes, which are rapidly growing.

BACKGROUND: The ability to regulate metabolism is a fundamental process in living systems. We present an analysis of one of the mechanisms by which metabolic regulation occurs: enzyme inhibition and activation by small molecules. We look at the network properties of this regulatory system and the relationship between the chemical properties of regulatory molecules. RESULTS: We find that many features of the regulatory network, such as the degree and clustering coefficient, closely match those of the underlying metabolic network. While these global features are conserved across several organisms, we do find local differences between regulation in E. coli and H. sapiens which reflect their different lifestyles. Chemical structure appears to play an important role in determining a compounds suitability for use in regulation. Chemical structure also often determines how groups of similar compounds can regulate sets of enzymes. These groups of compounds and the enzymes they regulate form modules that mirror the modules and pathways of the underlying metabolic network. We also show how knowledge of chemical structure and regulation could be used to predict regulatory interactions for drugs. CONCLUSION: The metabolic regulatory network shares many of the global properties of the metabolic network, but often varies at the level of individual compounds. Chemical structure is a key determinant in deciding how a compound is used in regulation and for defining modules within the regulatory system.

Mining frequent patterns is a general and important issue in data mining. Complex and unstructured (or semi-structured) datasets have appeared in major data mining applications, including text mining, web mining and bioinformatics. Mining patterns from these datasets is the focus of many of the current data mining approaches. We focus on labeled ordered trees, typical datasets of semi-structured data in data mining, and propose a new probabilistic model and its efficient learning scheme for mining labeled ordered trees. The proposed approach significantly improves the time and space complexity of an existing probabilistic modeling for labeled ordered trees, while maintaining its expressive power. We evaluated the performance of the proposed model, comparing it with that of the existing model, using synthetic as well as real datasets from the field of glycobiology. Experimental results showed that the proposed model drastically reduced the computation time of the competing model, keeping the predictive power and avoiding overfitting to the training data. Finally, we assessed our results using the proposed model on real data from a variety of biological viewpoints, verifying known facts in glycobiology.

MOTIVATION: The computational prediction of protein-protein interactions is currently a major issue in bioinformatics. Recently, a variety of co-evolution-based methods have been investigated toward this goal. In this study, we introduced a partial correlation coefficient as a new measure for the degree of co-evolution between proteins, and proposed its use to predict protein-protein interactions. RESULTS: The accuracy of the prediction by the proposed method was compared with those of the original mirror tree method and the projection method previously developed by our group. We found that the partial correlation coefficient effectively reduces the number of false positives, as compared with other methods, although the number of false negatives increased in the prediction by the partial correlation coefficient. AVAILABILITY: The R script for the prediction of protein-protein interactions reported in this manuscript is available at http://timpani.genome.ad.jp/~parco/

BACKGROUND: Phage display is widely used in basic research such as the exploration of protein-protein interaction sites and networks, and applied research such as the development of new drugs, vaccines, and diagnostics. It has also become a promising method for epitope mapping. Research on new algorithms that assist and automate phage display based epitope mapping has attracted many groups. Most of the existing tools have not been implemented as an online service until now however, making it less convenient for the community to access, utilize, and evaluate them. RESULTS: We present MIMOX, a free web tool that helps to map the native epitope of an antibody based on one or more user supplied mimotopes and the antigen structure. MIMOX was coded in Perl using modules from the Bioperl project. It has two sections. In the first section, MIMOX provides a simple interface for ClustalW to align a set of mimotopes. It also provides a simple statistical method to derive the consensus sequence and embeds JalView as a Java applet to view and manage the alignment. In the second section, MIMOX can map a single mimotope or a consensus sequence of a set of mimotopes, on to the corresponding antigen structure and search for all of the clusters of residues that could represent the native epitope. NACCESS is used to evaluate the surface accessibility of the candidate clusters; and Jmol is embedded to view them interactively in their 3D context. Initial case studies show that MIMOX can reproduce mappings from existing tools such as FINDMAP and 3DEX, as well as providing novel, rational results. CONCLUSION: A web-based tool called MIMOX has been developed for phage display based epitope mapping. As a publicly available online service in this area, it is convenient for the community to access, utilize, and evaluate, complementing other existing programs. MIMOX is freely available at http://web.kuicr.kyoto-u.ac.jp/~hjian/mimox.

BACKGROUND: Elementary mode analysis of metabolic pathways has proven to be a valuable tool for assessing the properties and functions of biochemical systems. However, little comprehension of how individual elementary modes are used in real cellular states has been achieved so far. A quantitative measure of fluxes carried by individual elementary modes is of great help to identify dominant metabolic processes, and to understand how these processes are redistributed in biological cells in response to changes in environmental conditions, enzyme kinetics, or chemical concentrations. RESULTS: Selecting a valid decomposition of a flux distribution onto a set of elementary modes is not straightforward, since there is usually an infinite number of possible such decompositions. We first show that two recently introduced decompositions are very closely related and assign the same fluxes to reversible elementary modes. Then, we show how such decompositions can be used in combination with kinetic modelling to assess the effects of changes in enzyme kinetics on the usage of individual metabolic routes, and to analyse the range of attainable states in a metabolic system. This approach is illustrated by the example of yeast glycolysis. Our results indicate that only a small subset of the space of stoichiometrically feasible steady states is actually reached by the glycolysis system, even when large variation intervals are allowed for all kinetic parameters of the model. Among eight possible elementary modes, the standard glycolytic route remains dominant in all cases, and only one other elementary mode is able to gain significant flux values in steady state. CONCLUSION: These results indicate that a combination of structural and kinetic modelling significantly constrains the range of possible behaviours of a metabolic system. All elementary modes are not equal contributors to physiological cellular states, and this approach may open a direction toward a broader identification of physiologically relevant elementary modes among the very large number of stoichiometrically possible modes.

BACKGROUND: In bio-systems, genes, proteins and compounds are related to each other, thus forming complex networks. Although each organism has its individual network, some organisms contain common sub-networks based on function. Given a certain sub-network, the distribution of organisms common to it represents the diversity of its function. RESULTS: We extracted such "common" sub-networks, defined as "phylogenetic network modules," using phylogenetic profiles and cluster analysis. The enzymes in the same "phylogenetic network module" have similar phylogenetic profiles and related functions. These modules are shown to be phylogenetic building blocks. Furthermore, the network of the modules illustrated hierarchical feature as well as the network of enzymes involved in the metabolism. CONCLUSION: We conclude that phylogenetic network modules are evolutionary conserved functional units in the metabolic network. We claim that our concept of phylogenetic modules provides a more accurate understanding of the evolution of biological networks.

MOTIVATION: Glycans are the third major class of biomolecules following DNA and proteins. They are extremely vital for the functioning of multicellular organisms. However, comparing the fast development of sequence analysis techniques, informatics work on glycans have a long way to go. Alignment algorithms for glycan tree structures are one of the foremost concerns. In addition, the statistical analysis of these algorithms in terms of biological significance needs to be addressed. RESULTS: We developed a tree-structure alignment algorithm for glycans and performed a statistical analysis of these alignment scores such that biologically interesting features could be captured into a score matrix for glycans. We generated our score matrix in a manner similar to BLOSUM, but with slight variations to accomodate our glycan data, including the incorporation of linkage information. We verified the effectiveness of our new glycan score matrix by illustrating how well the resulting score matrix entries correspond with biological knowledge. Future work for even better improvements with the use of a variety of score matrices for different subclasses of glycans due to their complexity is also discussed. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: The glycan score matrix can be downloaded from http://kanehisa.kuicr.kyoto-u.ac.jp/Paper/kcam/glycanMatrix0.1.txt.

MOTIVATION: It is widely recognized that homology search and ortholog clustering are very useful for analyzing biological sequences. However, recent growth of sequence database size makes homolog detection difficult, and rapid and accurate methods are required. RESULTS: We present a novel method for fast and accurate homology detection, assuming that the Smith-Waterman (SW) scores between all similar sequence pairs in a target database are computed and stored. In this method, SW alignment is computed only if the upper bound, which is derived from our novel inequality, is higher than the given threshold. In contrast to other methods such as FASTA and BLAST, this method is guaranteed to find all sequences whose scores against the query are higher than the specified threshold. Results of computational experiments suggest that the method is dozens of times faster than SSEARCH if genome sequence data of closely related species are available.

MOTIVATION: Glycan chains are synthesized by a combination of several kinds of glycosyltransferases (GTs). Thus, once we know the repertoire of GTs in the genome, in the transcriptome or in the proteome, it should in principle be possible to predict the repertoire of possible glycan structures in an organism or at a specific stage of the cell. Here, we show that a repertoire of glycan structures can be predicted from the set of GTs in the transcriptome. That is, using knowledge about glycan structure characteristics, we can predict glycan structures from incomplete or noisy data such as DNA microarray data. RESULTS: First, we constructed a reaction pattern library consisting of bond-formation patterns of GT reactions and investigated the co-occurrence frequencies of all reaction patterns in the glycan database. This was followed by the prediction of glycan structures using this library and a co-occurrence score. A penalty score was also implemented in the prediction method. Then we examined the performance of prediction by the leave-one-out cross validation method using individual reaction pattern profiles in the KEGG GLYCAN database as virtual expression profiles. The accuracy of prediction was 81%. Finally, we applied the prediction method to real expression data. Using expression profiles from the human carcinoma cell, glycan structures with sialic acid and sialyl Lewis X epitope were predicted, which corresponded well with experimental results.

MOTIVATION: The prediction of protein-protein interactions is currently an important issue in bioinformatics. The mirror tree method uses evolutionary information to predict protein-protein interactions. However, it has been recognized that predictions by the mirror tree method lead to many false positives. The incentive of our study was to solve this problem by improving the method of extracting the co-evolutionary information regarding the protein pairs. RESULTS: We developed a novel method to predict protein-protein interactions from co-evolutionary information in the framework of the mirror tree method. The originality is the use of the projection operator to exclude the information about the phylogenetic relationships among the source organisms from the distance matrix. Each distance matrix was transformed into a vector for the operation. The vector is referred to as a 'phylogenetic vector'. We have proposed three ways to extract the phylogenetic information: (1) using the 16S rRNA from the same source organisms as the proteins under consideration, (2) averaging the phylogenetic vectors and (3) analyzing the principal components of the phylogenetic vectors. We examined the performance of the proposed methods to predict interacting protein pairs from Escherichia coli, using experimentally verified data. Our method was successful, and it drastically reduced the number of false positives in the prediction. AVAILABILITY: The R script for the prediction of protein-protein interactions reported in this manuscript is available at http://timpani.genome.ad.jp/~proj/ CONTACT: [email protected] SUPPLEMENTARY INFORMATION: The information is also available at the same site as the R script.

BACKGROUND: Many real networks can be understood as two complementary networks with two kind of nodes. This is the case of metabolic networks where the first network has chemical compounds as nodes and the second one has nodes as reactions. In general, the second network may be related to the first one by a technique called line graph transformation (i.e., edges in an initial network are transformed into nodes). Recently, the main topological properties of the metabolic networks have been properly described by means of a hierarchical model. While the chemical compound network has been classified as hierarchical network, a detailed study of the chemical reaction network had not been carried out. RESULTS: We have applied the line graph transformation to a hierarchical network and the degree-dependent clustering coefficient C(k) is calculated for the transformed network. C(k) indicates the probability that two nearest neighbours of a vertex of degree k are connected to each other. While C(k) follows the scaling law C(k) approximately k(-1.1) for the initial hierarchical network, C(k) scales weakly as k0.08 for the transformed network. This theoretical prediction was compared with the experimental data of chemical reactions from the KEGG database finding a good agreement. CONCLUSIONS: The weak scaling found for the transformed network indicates that the reaction network can be identified as a degree-independent clustering network. By using this result, the hierarchical classification of the reaction network is discussed.

MOTIVATION: The subcellular location of a protein is closely correlated to its function. Thus, computational prediction of subcellular locations from the amino acid sequence information would help annotation and functional prediction of protein coding genes in complete genomes. We have developed a method based on support vector machines (SVMs). RESULTS: We considered 12 subcellular locations in eukaryotic cells: chloroplast, cytoplasm, cytoskeleton, endoplasmic reticulum, extracellular medium, Golgi apparatus, lysosome, mitochondrion, nucleus, peroxisome, plasma membrane, and vacuole. We constructed a data set of proteins with known locations from the SWISS-PROT database. A set of SVMs was trained to predict the subcellular location of a given protein based on its amino acid, amino acid pair, and gapped amino acid pair compositions. The predictors based on these different compositions were then combined using a voting scheme. Results obtained through 5-fold cross-validation tests showed an improvement in prediction accuracy over the algorithm based on the amino acid composition only. This prediction method is available via the Internet.

We present an algorithm to extract features from high-dimensional gene expression profiles, based on the knowledge of a graph which links to- gether genes known to participate to successive reactions in metabolic pathways. Motivated by the intuition that biologically relevant features are likely to exhibit smoothness with respect to the graph topology, the algorithm involves encoding the graph and the set of expression pro- files into kernel functions, and performing a generalized form of canoni- cal correlation analysis in the corresponding reproducible kernel Hilbert spaces. Function prediction experiments for the genes of the yeast S. Cerevisiae validate this approach by showing a consistent increase in performance when a state-of-the-art classifier uses the vector of features instead of the original expression profile to predict the functional class of a gene.

The sequence comparison has been the most fundamental method for understanding molecular functions encoded in the sequence data of proteins and nucleic acids. In general, however, the biological function results from an ordered network of interacting molecules in the cell; it cannot be attributed to just a single protein or a single gene. With the availability of complete genome sequences, it is now necessary to analyze multiple proteins or multiple genes at a time in order to understand higher level cellular functions, such as metabolism, signal transduction, cell cycle, apoptosis, and development.

MOTIVATION: The existing molecular biology databases focus on the sequence and structural aspects of biological macromolecules, i.e. DNAs, RNAs and proteins. However, in order to understand the functional aspects, it is essential to computerize the interaction of these molecules. Furthermore, living cells contain additional molecules, such as metabolic compounds and metal ions, that may also be considered as parts of the basic building blocks of life, but are not well organized in public databases. LIGAND chemical database is our attempt to solve these problems, at least for enzymatic reactions. RESULTS: LIGAND consists of two sections: ENZYME and COMPOUND. The ENZYME section is an extension of previous studies (Suyama et al. , Comput. Applic. Biosci., 9, 9-15, 1993), and it is a flat-file representation of 3303 enzymes and 2976 enzymatic reactions in the chemical equation format that can be parsed by machine. The COMPOUND section has been newly constructed for information on the nomenclature and chemical structures of compounds. It contains 5383 chemical compounds. Both ENZYME and COMPOUND entries contain rich cross-reference information, most of which is automatically generated by the DBGET/LinkDB system, thus providing the linkage between chemical and biological databases. LIGAND is updated daily, tightly coupled with the KEGG metabolic pathway database, and forms the basis for reconstruction and computation of pathways. AVAILABILITY: LIGAND can be accessed through the DBGET/LinkDB and KEGG systems in the Japanese GenomeNet database service via http://www.genome.ad.jp/. The flat-file format of the LIGAND database can be downloaded by anonymous FTP via ftp://kegg. genome.adjp/molecules/ligand/. CONTACT: [email protected]; [email protected]; [email protected]

We have developed simulated annealing algorithms to solve the problem of multiple sequence alignment. The algorithm was shown to give the optimal solution as confirmed by the rigorous dynamic programming algorithm for three-sequence alignment. To overcome long execution times for simulated annealing, we utilized a parallel computer. A sequential algorithm, a simple parallel algorithm and the temperature parallel algorithm were tested on a problem. The results were compared with the result obtained by a conventional tree-based algorithm where alignments were merged by two-way dynamic programming. Every annealing algorithm produced a better energy value than the conventional algorithm. The best energy value, which probably represents the optimal solution, was reached within a reasonable time by both of the parallel annealing algorithms. We consider the temperature parallel algorithm of simulated annealing to be the most suitable for finding the optimal multiple sequence alignment because the algorithm does not require any scheduling for optimization. The algorithm is also useful for refining multiple alignments obtained by other heuristic methods.

A procedure to detect similar local structures of proteins from C alpha coordinates is presented. First, the conformations of seven-residue peptide segments are approximated by a limited number of representatives, each of which is assigned a symbol. Thus, the overall conformation of a protein is represented by a symbol string. The comparison of these symbol strings using a sequence alignment technique then gives pairs of similar local structures. These pairs are considered candidates of structural motifs. The application of the procedure to the analysis of 93 proteins gave 858 pairs of similar local structures, which included several well-known structural motifs such as the nucleotide-binding beta alpha beta-unit and the calcium-binding EF hand. The characterization of amino acid patterns of similar local structures given by the procedure should be useful for the development of protein structure prediction based on the acquisition of empirical rules from a large-scale database.

We have previously developed a general method based on the statistical technique of discriminant analysis to predict splice junctions in eukaryotic mRNA sequences [Nakata, K., Kanehisa, M. and DeLisi, C. (1985) Nucleic Acids Res., 13, 5327-5340]. In order to evaluate further applicability of this method, we now analyze the promoter region of Escherichia coli sequences. The attributes used for discrimination include the accuracy of consensus sequence patterns measured by the perceptron algorithm, the thermal stability map, the base composition and the Calladine-Dickerson rules for helical twist angle, roll angle, torsion angle and propeller twist angle. When applied to selected E. coli sequences in the GenBank database, the method correctly identifies 75% of the true promoter regions.

The GenBank nucleic acid sequence database is a computer-based collection of all published DNA and RNA sequences; it contains over five million bases in close to six thousand sequence entries drawn from four thousand five hundred published articles. Each sequence is accompanied by relevant biological annotation. The database is available either on magnetic tape, on floppy diskettes, on-line or in hardcopy form. We discuss the structure of the database, the extent of the data and the implications of the database for research on nucleic acids.