On the complexity of finding control strategies for Boolean networks

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

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

4 Citations (Scopus)

Abstract

This paper considers a problem of finding control strategies for Boolean networks, where Boolean networks have been used as a model of genetic networks. This paper shows that finding a control strategy leading to the desired global state is NP-hard even if there is only one control node in the network. This result justifies existing exponential time algorithms for finding control strategies for probabilistic Boolean networks. On the other hand, this paper shows that the problem can be solved in polynomial time if the network has a tree structure.

Original languageEnglish
Title of host publicationProceedings of the 4th Asia-Pacific Bioinformatics Conference, APBC 2006
Pages99-108
Number of pages10
Publication statusPublished - 2006
Event4th Asia-Pacific Bioinformatics Conference, APBC 2006 - Taipei, Taiwan, Province of China
Duration: 13 Feb 200616 Feb 2006

Publication series

NameSeries on Advances in Bioinformatics and Computational Biology
Volume3
ISSN (Print)1751-6404

Conference

Conference4th Asia-Pacific Bioinformatics Conference, APBC 2006
Country/TerritoryTaiwan, Province of China
CityTaipei
Period13/02/0616/02/06

Scopus Subject Areas

  • Bioengineering
  • Information Systems

Fingerprint

Dive into the research topics of 'On the complexity of finding control strategies for Boolean networks'. Together they form a unique fingerprint.

Cite this