Biomedical subjects

Tatsuya Akutsu

Publications and source records attributed to Tatsuya Akutsu.

25 records · Page 2Linked to original sources

PubMed2004

A simple method for inferring strengths of protein-protein interactions.

Various computational methods have been proposed for inference of protein-protein interactions since protein-protein interaction plays an essential role in many cellular processes. One of well-studied approaches is to infer protein-protein interactions based on domain-domain interactions. To extend this approach, we proposed a method called LPNM to infer ratios of interactions, which outperformed other existing methods in terms of error of predicted ratios. However, since the LPNM method is based on the linear programming approach, it may require a large amount of time to infer interactions for a large data set. In this paper, we propose a simple method to infer the ratios of protein-protein interactions based on the association method by Sprinzak et al. In an experiment with a data set of protein-protein interactions in yeast, it runs more than 150 times as fast as the LPNM method, and achieves almost the same accuracy. On implementing algorithms for the inference problem, it is essential to understand how difficult the problem is. Even though various methods for the problem have been already proposed, it has not been analyzed rigorously from a computational point of view. We hence define a problem to maximize correctly classified examples, and prove the problem is MAX SNP-hard, which also means the problem is NP-hard.

Algorithms↗

PubMed2004

Clustering of database sequences for fast homology search using upper bounds on alignment score.

Homology data are among the most important information used to predict the functions of unknown proteins and thus fast and accurate methods are needed. In this paper, we propose a new approach for fast and accurate homology search using pre-computed all-against-all similarity scores in a target database. We previously developed a method for derivation of an upper bound of the Smith-Waterman score (SW-score) between a query and a homolog candidate sequence using the SW-score between the candidate and a sequence similar to the query. In this paper, by using this upper bound, we first cluster the sequences in the target database so that upper bounds of SW-scores for all the members in the clusters are less than a given value and select representative sequences for respective clusters. Then, the query sequence is searched against the representative sequences and the upper bounds of SW-scores for respective clusters are estimated. Only if the upper bound is higher than a given threshold, SW-alignments are computed for all the sequences in the cluster. We performed computational experiments to test efficiency of the proposed method for the KEGG/GENES database using the KEGG/SSDB. The results suggest that our method is efficient for redundant databases that include multiple closely related species.

Algorithms↗

PubMed2003

Inferring strengths of protein-protein interactions from experimental data using linear programming.

MOTIVATION: Several computational methods have been proposed for inference of protein-protein interactions. Most of the existing methods assume that protein-protein interaction data are given as binary data (i.e. whether or not each protein pair interacts). However, multiple biological experiments are performed for the same protein pairs and thus the ratio (strength) of the number of observed interactions to the number of experiments is available for each protein pair. RESULTS: We propose a new method for inference of protein-protein interactions from such experimental data. This method tries to minimize the errors between the ratios of observed interactions and the predicted probabilities in training data, where this problem is formalized as a linear program based on a probabilistic model. We compared the proposed method with the association method, the EM method and the SVM-based method using real interaction data. It is shown that a variant of the method is comparable to existing methods for binary data. It is also shown that the method outperforms existing methods for numerical data. AVAILABILITY: Programs transforming input data into LP format files are available upon request.

Algorithms↗

PubMed2003

Finding optimal degenerate patterns in DNA sequences.

MOTIVATION: The problem of finding transcription factor binding sites in the upstream regions of given genes is algorithmically an interesting and challenging problem in computational biology. A degenerate pattern over a finite alphabet Sigma is a sequence of subsets of Sigma. A string over IUPAC nucleic acid codes is also a degenerate pattern over Sigma = {A, C, G, T}, and is used as one of the major patterns modeling transcription factor binding sites in the upstream regions of genes. However, it is known that the problem of finding a degenerate pattern consistent with both positive and negative string sets is in general NP-complete. Our aim is to devise a heuristic algorithm to find a degenerate pattern which is optimal for positive and negative string sets w.r.t. a given score function. RESULTS: We have proposed an enumerative algorithm called SUPERPOSITION for finding optimal degenerate patterns with a pruning technique, which works with most all reasonable score functions. The performance score of the algorithm has been compared with those of other popular motif-finding algorithms YMF, MEME and AlignACE on various sets of co-regulated genes of yeast. In the computational experiment, SUPERPOSITION has outperformed the others on several gene sets. AVAILABILITY: The python script SUPERPOSITION is available at http://www.math.kyushu-u.ac.jp/~om/softwares.html

Algorithms↗

PubMed2003

Efficient tree-matching methods for accurate carbohydrate database queries.

One aspect of glycome informatics is the analysis of carbohydrate sugar chains, or glycans, whose basic structure is not a sequence, but a tree structure. Although there has been much work in the development of sequence databases and matching algorithms for sequences (for performing queries and analyzing similarity), the more complicated tree structure of glycans does not allow a direct implementation of such a database for glycans, and further, does not allow for the direct application of sequence alignment algorithms for performing searches or analyzing similarity. Therefore, we have utilized a polynomial-time dynamic programming algorithm for solving the maximum common subtree of two trees to implement an accurate and efficient tool for finding and aligning maximally matching glycan trees. The KEGG Glycan database for glycan structures released recently incorporates our tree-structure alignment algorithm with various parameters to adapt to the needs of a variety of users. Because we use similarity scores as opposed to a distance metric, our methods are more readily used to display trees of higher similarity. We present the two methods developed for this purpose and illustrate its validity.

Algorithms↗

PubMed2002

Point matching under non-uniform distortions and protein side chain packing based on an efficient maximum clique algorithm.

We developed maximum clique-based algorithms for spot matching for two-dimensional gel electrophoresis images, protein structure alignment and protein side-chain packing, where these problems are known to be NP-hard. Algorithms based on direct reductions to the maximum clique can find optimal solutions for instances of size (the number of points or residues) up to 50-150 using a standard PC. We also developed pre-processing techniques to reduce the sizes of graphs. Combined with some heuristics, many realistic instances can be solved approximately.

Algorithms↗

PubMedDate not supplied

Graph kernels for molecular structure-activity relationship analysis with support vector machines.

The support vector machine algorithm together with graph kernel functions has recently been introduced to model structure-activity relationships (SAR) of molecules from their 2D structure, without the need for explicit molecular descriptor computation. We propose two extensions to this approach with the double goal to reduce the computational burden associated with the model and to enhance its predictive accuracy: description of the molecules by a Morgan index process and definition of a second-order Markov model for random walks on 2D structures. Experiments on two mutagenicity data sets validate the proposed extensions, making this approach a possible complementary alternative to other modeling strategies.

Algorithms↗