Format

Send to

Choose Destination
IEEE/ACM Trans Comput Biol Bioinform. 2012 Sep-Oct;9(5):1410-21.

Finding a periodic attractor of a Boolean network.

Author information

1
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto, Japan. takutsu@kuicr.kyoto-u.ac.jp

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(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.

PMID:
22689081
DOI:
10.1109/TCBB.2012.87
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for IEEE Engineering in Medicine and Biology Society
Loading ...
Support Center