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

Tatsuya Akutsu*, Morihiro Hayashida, Wai Ki Ching, Kwok Po NG

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

379 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)670-679
Number of pages10
JournalJournal of Theoretical Biology
Volume244
Issue number4
DOIs
Publication statusPublished - 21 Feb 2007

Scopus Subject Areas

  • Statistics and Probability
  • Modelling and Simulation
  • Biochemistry, Genetics and Molecular Biology(all)
  • Immunology and Microbiology(all)
  • Agricultural and Biological Sciences(all)
  • Applied Mathematics

User-Defined Keywords

  • Boolean network
  • Control
  • Genetic network
  • NP-hard
  • Systems biology

Fingerprint

Dive into the research topics of 'Control of Boolean networks: Hardness results and algorithms for tree structured networks'. Together they form a unique fingerprint.

Cite this