Search

In this study, we address the problem of clustering string data in an unsupervised manner by developing a theory of a mixture model and an EM algorithm for string data based on probability theory on a topological monoid of strings developed in our previous studies. We first construct a parametric distribution on a set of strings in the motif of the Laplace distribution on a set of real numbers and reveal its basic properties. This Laplace-like distribution has two parameters: a string that represents the location of the distribution and a positive real number that represents the dispersion. It is difficult to explicitly write maximum likelihood estimators of the parameters because their log likelihood function is a complex function, the variables of which include a string; however, we construct estimators that almost surely converge to the maximum likelihood estimators as the number of observed strings increases and demonstrate that the estimators strongly consistently estimate the parameters. Next, we develop an iteration algorithm for estimating the parameters of the mixture model of the Laplace-like distributions and demonstrate that the algorithm almost surely converges to the EM algorithm for the Laplace-like mixture and strongly consistently estimates its parameters as the numbers of observed strings and iterations increase. Finally, we derive a procedure for unsupervised string clustering from the Laplace-like mixture that is asymptotically optimal in the sense that the posterior probability of making correct classifications is maximized., Comment: 56 pages

For understanding biological cellular systems, it is important to analyze interactions between protein residues and RNA bases. A method based on conditional random fields (CRFs) was developed for predicting contacts between residues and bases, which receives multiple sequence alignments for given protein and RNA sequences, respectively, and learns the model with many parameters involved in relationships between neighboring residue-base pairs by maximizing the pseudo likelihood function. In this paper, we proposed a novel CRF-based model with more complicated dependency relationships between random variables than the previous model, but which takes less parameters for the sake of avoidance of overfitting to training data. We performed cross-validation experiments for evaluating the proposed model, and took the average of AUC (area under receiver operating characteristic curve) scores. The result suggests that the proposed CRF-based model without using L1-norm regularization (lasso) outperforms the existing model with and without the lasso under several input observations to CRFs. We proposed a novel stochastic model for predicting protein-RNA residue-base contacts, and improved the prediction accuracy in terms of the AUC score. It implies that more dependency relationships in a CRF could be controlled by less parameters.

Enumeration of chemical structures satisfying given conditions is an important step in the discovery of new compounds and drugs, as well as the elucidation of the structure. One of the most frequently used conditions in the enumeration is the number of chemical elements that corresponds to the chemical formula. In this work, we propose a novel efficient enumeration algorithm, BfsStructEnum, which allows users to define desired cyclic structures and enumerates all nonredundant chemical compounds containing only defined structures as cyclic structures from a given chemical formula. To evaluate the performance, we confirm the number of enumerated structures of BfsStructEnum and MOLGEN 5.0, the latest version of a general-purpose structure generator. We also compare the computation time of BfsStructEnum with that of MOLGEN 5.0. The findings show that, given the same number of enumerated structures as MOLGEN 5.0, BfsStructEnum is significantly faster. By compressing a cyclic structure into a single node and representing chemical compounds by tree structures instead of normal graphs, the enumeration can be executed more efficiently.

The prediction of protein complexes from protein-protein interactions (PPIs) is a well-studied problem in bioinformatics. However, the currently available PPI data is not enough to describe all known protein complexes. In this paper, we express the problem of determining the minimum number of (additional) required protein-protein interactions as a graph theoretic problem under the constraint that each complex constitutes a connected component in a PPI network. For this problem, we develop two computational methods: one is based on integer linear programming (ILPMinPPI) and the other one is based on an existing greedy-type approximation algorithm (GreedyMinPPI) originally developed in the context of communication and social networks. Since the former method is only applicable to datasets of small size, we apply the latter method to a combination of the CYC2008 protein complex dataset and each of eight PPI datasets (STRING, MINT, BioGRID, IntAct, DIP, BIND, WI-PHI, iRefIndex). The results show that the minimum number of additional required PPIs ranges from 51 (STRING) to 964 (BIND), and that even the four best PPI databases, STRING (51), BioGRID (67), WI-PHI (93) and iRefIndex (85), do not include enough PPIs to form all CYC2008 protein complexes. We also demonstrate that the proposed problem framework and our solutions can enhance the prediction accuracy of existing PPI prediction methods. ILPMinPPI can be freely downloaded from http://sunflower.kuicr.kyoto-u.ac.jp/~nakajima/.

For a data set composed of numbers or numerical vectors, a mean is the most fundamental measure for capturing the center of the data. However, for a data set of strings, a mean of the data cannot be defined, and therefore, median and center strings are frequently used as a measure of the center of the data. In contrast to calculating a mean of numerical data, constructing median and center strings of string data is not easy, and no algorithm is found that is guaranteed to construct exact solutions of center strings. In this study, we first generalize the definitions of median and center strings of string data into those of a probability distribution on a set of all strings composed of letters in a given alphabet. This generalization corresponds to that of a mean of numerical data into an expected value of a probability distribution on a set of numbers or numerical vectors. Next, we develop methods for constructing exact solutions of median and center strings for a probability distribution on a set of strings, applying integer linear programming. These methods are improved into faster ones by using the triangle inequality on the Levenshtein distance in the case where a set of strings is a metric space with the Levenshtein distance. Furthermore, we also develop methods for constructing approximate solutions of median and center strings very rapidly if the probability of a subset composed of similar strings is close to one. Lastly, we perform simulation experiments to examine the usefulness of our proposed methods in practical applications.

Numbers and numerical vectors account for a large portion of data. However, recently the amount of string data generated has increased dramatically. Consequently, classifying string data is a common problem in many fields. The most widely used approach to this problem is to convert strings into numerical vectors using string kernels and subsequently apply a support vector machine that works in a numerical vector space. However, this non-one-to-one conversion involves a loss of information and makes it impossible to evaluate, using probability theory, the generalization error of a learning machine, considering that the given data to train and test the machine are strings generated according to probability laws. In this study, we approach this classification problem by constructing a classifier that works in a set of strings. To evaluate the generalization error of such a classifier theoretically, probability theory for strings is required. Therefore, we first extend a limit theorem on the asymptotic behavior of a consensus sequence of strings, which is the counterpart of the mean of numerical vectors, as demonstrated in the probability theory on a metric space of strings developed by one of the authors and his colleague in a previous study [18]. Using the obtained result, we then demonstrate that our learning machine classifies strings in an asymptotically optimal manner. Furthermore, we demonstrate the usefulness of our machine in practical data analysis by applying it to predicting protein--protein interactions using amino acid sequences., This manuscript has been withdrawn because the experiments in Section 6 are insufficient

We address problems of finding median and center strings for a probability distribution on a set of strings under Levenshtein distance, which are known to be NP-hard in a special case. There are many applications in various research fields, for instance, to find functional motifs in protein amino acid sequences, and to recognize shapes and characters in image processing. In this paper, we propose novel integer linear programming-based methods for finding median and center strings for a probability distribution on a set of strings under Levenshtein distance. Furthermore, we restrict several variables to a region near the diagonal in the formulation, and propose novel integer linear programming-based methods also for finding approximate median and center strings for a probability distribution on a set of strings. For evaluation of our proposed methods, we perform several computational experiments, and show that the restricted formulation reduced the execution time.

Many mathematical models for gene regulatory networks have been proposed. In this study, the authors study attractors in probabilistic Boolean networks (PBNs). They study the expected number of singleton attractors in a PBN and show that it is (2 - (1/2)(L-1))(n), where n is the number of nodes in a PBN and L is the number of Boolean functions assigned to each node. In the case of L=2, this number is simplified into 1.5(n). It is an interesting result because it is known that the expected number of singleton attractors in a Boolean network (BN) is 1. Then, we present algorithms for identifying singleton and small attractors and perform both theoretical and computational analyses on their average case time complexities. For example, the average case time complexities for identifying singleton attractors of a PBN with L=2 and L=3 are O(1.601(n)) and O(1.763(n)), respectively. The results of computational experiments suggest that these algorithms are much more efficient than the naive algorithm that examines all possible 2(n) states.

Finding control strategies of cells is a challenging and important problem in the post-genomic era. This paper considers theoretical aspects of the control problem using the Boolean network (BN), which is a simplified model of genetic networks. It is shown that finding a control strategy leading to the desired global state is computationally intractable (NP-hard) in general. Furthermore, this hardness result is extended for BNs with considerably restricted network structures. These results justify existing exponential time algorithms for finding control strategies for probabilistic Boolean networks (PBNs). On the other hand, this paper shows that the control problem can be solved in polynomial time if the network has a tree structure. Then, this algorithm is extended for the case where the network has a few loops and the number of time steps is small. Though this paper focuses on theoretical aspects, biological implications of the theoretical results are also discussed.

The protein threading problem with profiles is known to be efficiently solvable using dynamic programming. In this paper, we consider a variant of the protein threading problem with profiles in which constraints on distances between residues are given. We prove that protein threading with profiles and constraints is NP-hard. Moreover, we show a strong hardness result on the approximation of an optimal threading satisfying all the constraints. On the other hand, we develop two practical algorithms: CLIQUETHREAD and BBDPTHREAD. CLIQUETHREAD reduces the threading problem to the maximum edge-weight clique problem, whereas BBDPTHREAD combines dynamic programming and branch-and-bound techniques. We perform computational experiments using protein structure data in PDB (Protein Data Bank) using simulated distance constraints. The results show that constraints are useful to improve the alignment accuracy of the target sequence and the template structure. Moreover, these results also show that BBDPTHREAD is in general faster than CLIQUETHREAD for larger size proteins whereas CLIQUETHREAD is useful if there does not exist a feasible threading.

nding of protein structures is important to find their functions. Many methods such as alignment, alignment-free similarity, and use of structural fragments have been developed for finding similar protein structures. In our previous study, we transformed protein structures into images each pixel of which represents the distance between the corre­ sponding C" atoms, and proposed similarity measures between two protein structures based on Kolmogorov complexity using image compression algorithms. In this paper, we examine efficient and effective image recognition techniques, SIFT (Scale Invariant Feature Transform) and SURF (Speeded Up Robust Features), which are invariant to image scaling, translation, and rotation, and partially invariant to affine or three-dimensiona l projection. We propose similarity based on SIFT and SURF, and apply it to classification of several protein structures. The results suggest that the similarity based on SURF outperforms several existing similarity measures including the compression-base d similarity measures in our previous study, and that SIFT and SURF are useful for recognizing protein structures as well as objects in images.

Molecular enumeration plays a basic role in the design of drugs, which has been studied by mathematicians, computer scientists, and chemists for quite a long time. Although many researchers are involved in developing enumeration algorithms specific to drug design systems, molecular enumeration is still a hard problem to date due to its exponentially increasing large search space with larger number of atoms. To alleviate this defect, we propose efficient algorithms, BfsSimEnum and BfsMulEnum to enumerate tree-like molecules without and with multiple bonds, respectively, where chemical compounds are represented as molecular graphs. In order to reduce the large search space, we adjust some important concepts such as left-heavy, center-rooted, and normal form to molecular tree graphs. Different from many existing approaches, BfsSimEnum and BfsMulEnum firstly enumerate tree-like compounds by breadth-first search order. Computational experiments are performed to compare with several existing methods. The results suggest that our proposed methods are exact and more efficient.

Since many proteins express their functional activity by interacting with other proteins and forming protein complexes, it is very useful to identify sets of proteins that form complexes. For that purpose, many prediction methods for protein complexes from protein-protein interactions have been developed such as MCL, MCODE, RNSC, PCP, RRW, and NWE. These methods have dealt with only complexes with size of more than three because the methods often are based on some density of subgraphs. However, heterodimeric protein complexes that consist of two distinct proteins occupy a large part according to several comprehensive databases of known complexes. In this paper, we propose several feature space mappings from protein-protein interaction data, in which each interaction is weighted based on reliability. Furthermore, we make use of prior knowledge on protein domains to develop feature space mappings, domain composition kernel and its combination kernel with our proposed features. We perform ten-fold cross-validation computational experiments. These results suggest that our proposed kernel considerably outperforms the naive Bayes-based method, which is the best existing method for predicting heterodimeric protein complexes.

One of the important topics in systems biology is to develop theory and methods for control of biological networks, which might lead to development of novel treatment methods for difficult diseases. On the other hand, the Boolean network (BN) model is known as a mathematical model of genetic networks. Though many studies have been done on analysis of steady states (i.e., attractors) in BNs, only a few studies have been done on control of BNs. In this paper, we consider three problems on BNs: detection of a singleton attractor, finding a control strategy that brings a BN from a given initial state to the desired state, and control of attractors. We propose integer programming-based methods which solve these problems in a unified manner. We also present results of computational experiments, which suggest that the proposed methods are useful for solving moderate size instances of these problems.

Proteins are essential molecules of life in the cell and are involved in multiple and highly specialized tasks encoded in the amino acid sequence. In particular, protein function is closely related to fundamental units of protein structure called domains. Here, we investigate the distribution of kinds of domains in human cells. Our findings show that while the number of domain types shared by k proteins follows a scale-free distribution, the number of proteins composed of k types of domains decays as an exponential distribution. In contrast, previous data analyses and mathematical modeling reported a scale-free distribution for the protein domain distribution because the relation between kinds of domains and the number of domains in a protein was not considered. Based on this finding, we have developed an evolutionary model based on (1) growth process and (2) copy mechanism that explains the emergence of this mixing of exponential and scale-free distributions.

Boolean networks (BNs) are known as a mathematical model of genetic networks. In this paper, we overview algorithmic aspects of inference, analysis and control of BNs while focusing on the authors' works. For inference of BN, we review results on the sample complexity required to uniquely identify a BN. For analysis of BN, we review efficient algorithms for identifying singleton attractors. For control of BN, we review NP-hardness results and dynamic programming algorithms for general and special cases.

This paper considers the problem of finding global states incoming to a specified global state in a Boolean network, which may be useful for pre-processing of finding a sequence of control actions for a Boolean network and for identifying the basin of attraction for a given attractor. We show that this problem is NP-hard in general along with related theoretical results. On the other hand, we present algorithms that are much faster than the naive exhaustive search-based algorithm.

This paper considers a problem of finding control strategies for Boolean networks, where Boolean networks have been used as a model of genetic networks. This paper shows that finding a control strategy leading to the desired global state is NP-hard even if there is only one control node in the network. This result justifies existing exponential time algorithms for finding control strategies for probabilistic Boolean networks. On the other hand, this paper shows that the problem can be solved in polynomial time if the network has a tree structure.

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.

Complex systems arise in many different contexts from large communication systems and transportation infrastructures to molecular biology. Most of these systems can be organized into networks composed of nodes and interacting edges. Here, we present a theoretical model that constructs bipartite networks with the particular feature that the degree distribution can be tuned depending on the probability rate of fundamental processes. We then use this model to investigate protein-domain networks. A protein can be composed of up to hundreds of domains. Each domain represents a conserved sequence segment with specific functional tasks. We analyze the distribution of domains in Homo sapiens and Arabidopsis thaliana organisms and the statistical analysis shows that while (a) the number of domain types shared by k proteins exhibits a power-law distribution, (b) the number of proteins composed of k types of domains decays as an exponential distribution. The proposed mathematical model generates bipartite graphs and predicts the emergence of this mixing of (a) power-law and (b) exponential distributions. Our theoretical and computational results show that this model requires (1) growth process and (2) copy mechanism.

In this paper, we consider the problem of selecting the most effective set of reporter genes for analysis of biological networks using cell microarrays. We propose two graph theoretic formulations of the reporter gene allocation problem, and show that both problems are hard to approximate. We propose integer programming-based methods for solving practical instances of these problems optimally. We apply them to apoptosis pathway maps, and discuss the biological significance of the result. We also apply them to artificial networks, the result of which shows that optimal solutions can be obtained within several seconds for networks with 10,000 nodes.