An improved satisfiability algorithm for nested canalyzing functions and its application to determining a singleton attractor of a Boolean network.
We study the problem of finding a 0-1 assignment to Boolean variables satisfying a given set of nested canalyzing functions, a class of Boolean functions that is known to be of interest in biology. For this problem, an extension of the satisfiability problem for a conjunctive normal form formula, an O(min(2(k), 2((k+m)/2))poly(m)) time algorithm has been known, where m and k are the number of nested canalyzing functions and variables, respectively. Here we present an improved O(min(2(k), 1.325(k+m), 2(m))poly(m)) time algorithm for this problem. We also study the problem of finding a singleton attractor of a Boolean network consisting of n nested canalyzing functions. Although an O(1.799(n)) time algorithm was proposed in a previous study, it was implicitly assumed that the network does not contain any positive self-loops. By utilizing the improved satisfiability algorithm for nested canalyzing functions, while allowing for the presence of positive self-loops, we show that the general case can be solved in O(1.871(n)) time.
1 Department of Computer Science, Ben-Gurion University of the Negev , Beer-Sheva, Israel .
Avraham A
AA
Melkman
Tatsuya
T
Akutsu
D000465:Algorithms; D000818:Animals; D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D005786:Gene Expression Regulation; D053263:Gene Regulatory Networks; D006801:Humans; D008957:Models, Genetic; D015233:Models, Statistical; D049490:Systems Biology