Control of Boolean networks: Hardness results and algorithms for tree structured networks

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

Full description

Saved in:
Bibliographic Details
Published in:Journal of theoretical biology 2007-02, Vol.244 (4), p.670-679
Main Authors: Akutsu, Tatsuya, Hayashida, Morihiro, Ching, Wai-Ki, Ng, Michael K.
Format: Article
Language:English
Subjects:
Algorithms
Animals
Boolean network
Cell Physiological Phenomena
Control
Gene Expression Regulation
Genetic network
Logic
Models, Genetic
NP-hard
Probability
Systems Biology
Systems Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-5193
1095-8541
DOI:10.1016/j.jtbi.2006.09.023