Finding a Periodic Attractor of a Boolean Network

Author

Akutsu, Tatsuya ; Kosub, Sven ; Melkman, Avraham A. ; Tamura, Takeyuki

Author_Institution

Inst. for Chem. Res., Kyoto Univ., Kyoto, Japan

Volume

9

Issue

5

fYear

2012

Firstpage

1410

Lastpage

1421

Abstract

In this paper, we study the problem of finding a periodic attractor of a Boolean network (BN), which arises in computational systems biology and is known to be NP-hard. Since a general case is quite hard to solve, we consider special but biologically important subclasses of BNs. For finding an attractor of period 2 of a BN consisting of n OR functions of positive literals, we present a polynomial time algorithm. For finding an attractor of period 2 of a BN consisting of n AND/OR functions of literals, we present an O(1.985ⁿ) time algorithm. For finding an attractor of a fixed period of a BN consisting of n nested canalyzing functions and having constant treewidth w, we present an O(n^2p(w+1)poly(n)) time algorithm.

Keywords

Boolean functions; biology computing; genetic algorithms; polynomials; AND-OR functions; Boolean network; computational systems biology; constant treewidth; nested canalyzing functions; periodic attractor; polynomial time algorithm; positive literals; time algorithm; Boolean functions; Computational systems biology; Polynomials; Boolean network; SAT; nested canalyzing function; periodic attractor; treewidth.; Algorithms; Gene Expression Profiling; Systems Biology;

fLanguage

English

Journal_Title

Computational Biology and Bioinformatics, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1545-5963

Type

jour

DOI

10.1109/TCBB.2012.87

Filename

6216351