Finding a Periodic Attractor of a Boolean Network

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

• Book ID: 117908655
• Publisher: IEEE
• Year: 2012
• Tongue: English
• Weight: 613 KB
• Volume: 9
• Category: Article
• ISSN: 1545-5963
• DOI: 10.1109/tcbb.2012.87

✦ Synopsis

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 n Þ 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.