Search

Background: Mathematical modeling has been applied to the study and analysis of complex biological systems for a long time. Some processes in biological systems, such as the gene expression and feedback control in signal transduction networks, involve a time delay. These systems are represented as delay differential equation (DDE) models. Numerical sensitivity analysis of a DDE model by the direct method requires the solutions of model and sensitivity equations with time-delays. The major effort is the computation of Jacobian matrix when computing the solution of sensitivity equations. The computation of partial derivatives of complex equations either by the analytic method or by symbolic manipulation is time consuming, inconvenient, and prone to introduce human errors. To address this problem, an automatic approach to obtain the derivatives of complex functions efficiently and accurately is necessary., Results: We have proposed an efficient algorithm with an adaptive step size control to compute the solution and dynamic sensitivities of biological systems described by ordinal differential equations (ODEs). The adaptive direct-decoupled algorithm is extended to solve the solution and dynamic sensitivities of time-delay systems describing by DDEs. To save the human effort and avoid the human errors in the computation of partial derivatives, an automatic differentiation technique is embedded in the extended algorithm to evaluate the Jacobian matrix. The extended algorithm is implemented and applied to two realistic models with time-delays: the cardiovascular control system and the TNF-α signal transduction network. The results show that the extended algorithm is a good tool for dynamic sensitivity analysis on DDE models with less user intervention., Conclusions: By comparing with direct-coupled methods in theory, the extended algorithm is efficient, accurate, and easy to use for end users without programming background to do dynamic sensitivity analysis on complex biological systems with time-delays.

Let T be a tree on a set V of nodes. The p- th power T of T is the graph on V such that any two nodes u and w of V are adjacent in T if and only if the distance of u and w in T is at most p. Given an n-node m-edge graph G and a positive integer p, the p- th tree root problem asks for a tree T, if any, such that G= T. Given an n-node m-edge graph G, the tree root problem asks for a positive integer p and a tree T, if any, such that G= T. Kearney and Corneil gave the best previously known algorithms for both problems. Their algorithm for the former (respectively, latter) problem runs in O( n) (respectively, O( n)) time. In this paper, we give O( n+ m)-time algorithms for both problems. [ABSTRACT FROM AUTHOR]

Abstract: Let denote a graph class. An undirected graph is called a probe graph if one can make a graph in by adding edges between vertices in some independent set of . By definition graph class is a subclass of probe graphs. A graph is distance hereditary if the distance between any two vertices remains the same in every connected induced subgraph. Bipartite distance-hereditary graphs are both bipartite and distance hereditary. In this paper we propose -time algorithms to recognize probe distance-hereditary graphs and probe bipartite distance-hereditary graphs where and are the numbers of vertices and edges of the input graph respectively. [Copyright &y& Elsevier]

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0< ε<1, by examining function values of f over o(| D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε| D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f, which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f. In this paper, we prove the existence of a set of quartet topologies of error number at least $c{n\choose 4}$ for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O( n/ ε) queries, and is of one-sided error and non-adaptive. [ABSTRACT FROM AUTHOR]

Abstract: Let be a class of graphs. A graph has -width if there are independent sets in such that can be embedded into a graph such that for every edge in which is not an edge in , there exists an such that both endvertices of are in . For the class of block graphs we show that graphs with -width at most 4 are perfect. We also show that -width is NP-complete and show that it is fixed-parameter tractable. For the class of complete graphs, similar results are also obtained. [Copyright &y& Elsevier]

Abstract: A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to test whether a graph has a Hamiltonian cycle. A path cover of a graph is a family of vertex-disjoint paths that covers all vertices of the graph. The path cover problem is to find a path cover of a graph with minimum cardinality. This paper presents -time certifying algorithms for the above two problems on interval graphs given a set of intervals with endpoints sorted. The certificates provided by our algorithms can be authenticated in time. [Copyright &y& Elsevier]

Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4 k n+ n4). In this paper, first we present an O(3.0446 k n+ n4) fixed-parameter algorithm and an O(2.0162 k n3+ n5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O*((1+ ε) k) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant. [ABSTRACT FROM AUTHOR]

Abstract: Given a class of graphs , a graph is a probe graph of if its vertices can be partitioned into a set of probes and an independent set of nonprobes such that can be embedded into a graph of by adding edges between certain nonprobes. If the partition of the vertices is part of the input, we call a partitioned probe graph of . In this paper we show that there exists a polynomial-time algorithm for the recognition of partitioned probe graphs of comparability graphs. This immediately leads to a polynomial-time algorithm for the recognition of partitioned probe graphs of cocomparability graphs. We then show that a partitioned graph is a partitioned probe permutation graph if and only if is at the same time a partitioned probe graph of comparability and cocomparability graphs. [Copyright &y& Elsevier]

Abstract: A path cover of a graph is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set of . The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O() time, to solve the path cover problem on distance-hereditary graphs. [Copyright &y& Elsevier]

Abstract: A path cover of a graph is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple -time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs. [Copyright &y& Elsevier]

The domination problem and its variants have been extensively studied in the literature. In this paper we investigate the domination problem in distance-hereditary graphs. In particular, we give a linear-time algorithm for the domination problem in distance-hereditary graphs by a labeling approach. We actually solve a more general problem, called the L-domination problem, which also includes the total domination problem as a special case. [Copyright &y& Elsevier]

.Polynomial-time algorithms for the feedback vertex set problem in cocomparability graphs and convex bipartite graphs are presented. [ABSTRACT FROM AUTHOR]