title: Determining a singleton attractor of a boolean network with nested canalyzing functions.
abstract: In this article, we study the problem of finding a singleton attractor for several biologically important subclasses of Boolean networks (BNs). The problem of finding a singleton attractor in a BN is known to be NP-hard in general. For BNs consisting of n nested canalyzing functions, we present an O(1.799(n)) time algorithm. The core part of this development is an O(min(2(k/2) · 2(m/2), 2(k)) · poly(k, m)) time algorithm for the satisfiability problem for m nested canalyzing functions over k variables. For BNs consisting of chain functions, a subclass of nested canalyzing functions, we present an O(1.619(n)) time algorithm and show that the problem remains NP-hard, even though the satisfiability problem for m chain functions over k variables is solvable in polynomial time. Finally, we present an o(2(n)) time algorithm for bounded degree BNs consisting of canalyzing functions.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyot, Japan. takutsu@kuicr.kyoto-u.ac.jp
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
authors.forename: Avraham A
authors.initials: AA
authors.lastname: Melkman
authors.forename: Takeyuki
authors.initials: T
authors.lastname: Tamura
authors.forename: Masaki
authors.initials: M
authors.lastname: Yamamoto
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D003198:Computer Simulation; D005786:Gene Expression Regulation; D007700:Kinetics; D008957:Models, Genetic; D017711:Nonlinear Dynamics; D049490:Systems Biology