Format

Send to

Choose Destination
J Theor Biol. 2007 Feb 21;244(4):670-9. Epub 2006 Sep 24.

Control of Boolean networks: hardness results and algorithms for tree structured networks.

Author information

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

Abstract

Finding control strategies of cells is a challenging and important problem in the post-genomic era. This paper considers theoretical aspects of the control problem using the Boolean network (BN), which is a simplified model of genetic networks. It is shown that finding a control strategy leading to the desired global state is computationally intractable (NP-hard) in general. Furthermore, this hardness result is extended for BNs with considerably restricted network structures. These results justify existing exponential time algorithms for finding control strategies for probabilistic Boolean networks (PBNs). On the other hand, this paper shows that the control problem can be solved in polynomial time if the network has a tree structure. Then, this algorithm is extended for the case where the network has a few loops and the number of time steps is small. Though this paper focuses on theoretical aspects, biological implications of the theoretical results are also discussed.

PMID:
17069859
DOI:
10.1016/j.jtbi.2006.09.023
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for Elsevier Science
Loading ...
Support Center