Finding fixed points in discrete dynamical systems is important because fixed points correspond to steady-states. The Boolean network is considered as one of the simplest discrete dynamical systems and is often used as a model of genetic networks. It is known that detection of a fixed point in a Boolean network with n nodes and maximum indegree K can be polynomially transformed into (K+1)-SAT with n variables. In this paper, we focus on the case of K=2 and present an O(1.3171n) expected time algorithm, which is faster than the naive algorithm based on a reduction to 3-SAT, where we assume that nodes with indegree 2 do not contain self-loops. We also show an algorithm for the general case of K=2 that is slightly faster than the naive algorithm.

The Boolean network (BN) can be used to create discrete mathematical models of gene regulatory networks. In this paper, we consider three problems on BNs that are known to be NP-hard: detection of a singleton attractor, finding a control strategy that shifts 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. Then, we present results of computational experiments which suggest that the proposed methods are useful for solving moderate size instances of these problems. We also show that control of attractors is -hard, which suggests that control of attractors is harder than the other two problems.

The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor, which is also called a fixed point, is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in O(n 2n) time, no O((2-ε)n) (ε > 0) time algorithm was known even for an AND/OR BN with non-restricted indegree, where n is the number of nodes in a BN. In this paper, we present an O(1.787n) time algorithm for detecting a singleton attractor of a given AND/OR BN, along with related results. We also show that detection of a singleton attractor in a BN with maximum indegree two is NP-hard and can be polynomially reduced to a satisfiability problem.

It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n3) time by using simple dynamic programming procedures. For this problem, an O(n3(log log n)1/2/(log n)1/2) time exact algorithm and an O(n2.776+(1/ε)O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n5) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.

In this paper, we consider the problem of inferring a Boolean network (BN) from a given set of singleton attractors, where it is required that the resulting BN has the same set of singleton attractors as the given one. We show that the problem can be solved in linear time if the number of singleton attractors is at most two and each Boolean function is restricted to be a conjunction or disjunction of literals. We also show that the problem can be solved in polynomial time if more general Boolean functions can be used. In addition to the inference problem, we study two network completion problems from a given set of singleton attractors: adding the minimum number of edges to a given network, and determining Boolean functions to all nodes when only network structure of a BN is given. In particular, we show that the latter problem cannot be solved in polynomial time unless P=NP, by means of a polynomial-time Turing reduction from the complement of the another solution problem for the Boolean satisfiability problem.

Metabolic networks represent the relationship between chemical reactions and compounds in cells. In useful metabolite production using microorganisms, it is often required to calculate reaction deletion strategies from the original network to result in growth coupling, which means the target metabolite production and cell growth are simultaneously achieved. Although simple elementary flux mode (EFM)-based methods are useful for listing such reaction deletions strategies, the number of cases to be considered is often proportional to the exponential function of the size of the network. Therefore, it is desirable to develop methods of narrowing down the number of reaction deletion strategy candidates. In this study, the author introduces the idea of L1 norm minimal modes to consider metabolic flows whose L1 norms are minimal to satisfy certain criteria on growth and production, and developed a fast metabolic design listing algorithm based on it (minL1-FMDL), which works in polynomial time. Computational experiments were conducted for (1) a relatively small network to compare the performance of minL1-FMDL with that of the simple EFM-based method and (2) a genome-scale network to verify the scalability of minL1-FMDL. In the computational experiments, it was seen that the average value of the target metabolite production rates of minL1-FMDL was higher than that of the simple EFM-based method, and the computation time of minL1-FMDL was fast enough even for genome-scale networks. The developed software, minL1-FMDL, implemented in MATLAB, is available on https://sunflower.kuicr.kyoto-u.ac.jp/~tamura/software, and can be used for genome-scale metabolic network design for metabolite production.

The impact degree is a measure of the robustness of a metabolic network against deletion of single or multiple reaction(s). Although such a measure is useful for mining important enzymes/genes, it was defined only for networks without cycles. In this paper, we extend the impact degree for metabolic networks containing cycles and develop a simple algorithm to calculate the impact degree. Furthermore we improve this algorithm to reduce computation time for the impact degree by deletions of multiple reactions. We applied our method to the metabolic network of E. coli, that includes reference pathways, consisting of 3281 reaction nodes and 2444 compound nodes, downloaded from KEGG database, and calculate the distribution of the impact degree. The results of our computational experiments show that the improved algorithm is 18.4 times faster than the simple algorithm for deletion of reaction-pairs and 11.4 times faster for deletion of reaction-triplets. We also enumerate genes with high impact degrees for single and multiple reaction deletions.

A reaction cut is a set of chemical reactions whose deletion blocks the operation of given reactions or the production of given chemical compounds. In this paper, we study two problems ReactionCut and MD-ReactionCut for calculating the minimum reaction cut of a metabolic network under a Boolean model. These problems are based on the flux balance model and the minimal damage model respectively. We show that ReactionCut and MD-ReactionCut are NP-hard even if the maximum outdegree of reaction nodes (Kout) is one. We also present O(1.822n), O(1.959n) and o(2n) time algorithms for MD-ReactionCut with Kout=2, 3, k respectively where n is the number of reaction nodes and k is a constant. The same algorithms also work for ReactionCut if there is no directed cycle. Furthermore, we present a 2O((log n)) time algorithm, which is faster than O((1+ε)n) for any positive constant ε, for the planar case of MD-ReactionCut under a reasonable constraint utilizing Lipton and Tarjan's separator algorithm.

In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigree graph and distance matrix of genetic distances.

The Boolean network can be used as a mathematical model for gene regulatory networks. An attractor, which is a state of a Boolean network repeating itself periodically, can represent a stable stage of a gene regulatory network. It is known that the problem of finding an attractor of the shortest period is NP-hard. In this article, we give a fixed-parameter algorithm for detecting a singleton attractor (SA) for a Boolean network that has only AND and OR Boolean functions of literals and has bounded treewidth k. The algorithm is further extended to detect an SA for a constant-depth nested canalyzing Boolean network with bounded treewidth. We also prove the fixed-parameter intractability of the detection of an SA for a general Boolean network with bounded treewidth.

In STS-based mapping, it is necessary to obtain the correct order of probes in a DNA sequence from a given set of fragments or an equivalently a hybridization matrix A. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of A's columns so that the resulting matrix has a consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order uniquely determines the correct order of the probes. Unfortunately this does not hold if the data include errors, and this has been a popular research target in computational biology. Even if there is no error, ambiguities in the probe order may still remain. This in fact happens because of the lack of some information regarding the data, but almost no further investigation has previously been made. In this paper, we define a measure of such imperfectness of the data as the minimum amount of the additional fragments that are needed to uniquely fix the probe order. Polynomial-time algorithms to compute such additional fragments of the minimum cost are presented. A computer simulation using genes of human chromosome 20 is also noted.