On the complexity of finding control strategies for Boolean networks

Tatsuya Akutsu; Morihiro Hayashida; Wai Ki Ching; Kwok Po Ng

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

Department of Mathematics

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

5 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 language	English
Title of host publication	Proceedings of the 4th Asia-Pacific Bioinformatics Conference, APBC 2006
Pages	99-108
Number of pages	10
Publication status	Published - 2006
Event	4th Asia-Pacific Bioinformatics Conference, APBC 2006 - Taipei, Taiwan, Province of China Duration: 13 Feb 2006 → 16 Feb 2006

Publication series

Name	Series on Advances in Bioinformatics and Computational Biology
Volume	3
ISSN (Print)	1751-6404

Conference

Conference	4th Asia-Pacific Bioinformatics Conference, APBC 2006
Country/Territory	Taiwan, Province of China
City	Taipei
Period	13/02/06 → 16/02/06

Scopus Subject Areas

Bioengineering
Information Systems

Cite this

@inproceedings{1ff0174517f14120b307ce71fd90e878,

title = "On the complexity of finding control strategies for Boolean networks",

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

author = "Tatsuya Akutsu and Morihiro Hayashida and Ching, {Wai Ki} and Ng, {Kwok Po}",

year = "2006",

language = "English",

isbn = "1860946232",

series = "Series on Advances in Bioinformatics and Computational Biology",

pages = "99--108",

booktitle = "Proceedings of the 4th Asia-Pacific Bioinformatics Conference, APBC 2006",

}

Akutsu, T, Hayashida, M, Ching, WK & Ng, KP 2006, On the complexity of finding control strategies for Boolean networks. in Proceedings of the 4th Asia-Pacific Bioinformatics Conference, APBC 2006. Series on Advances in Bioinformatics and Computational Biology, vol. 3, pp. 99-108, 4th Asia-Pacific Bioinformatics Conference, APBC 2006, Taipei, Taiwan, Province of China, 13/02/06.

On the complexity of finding control strategies for Boolean networks. / Akutsu, Tatsuya; Hayashida, Morihiro; Ching, Wai Ki et al.
Proceedings of the 4th Asia-Pacific Bioinformatics Conference, APBC 2006. 2006. p. 99-108 (Series on Advances in Bioinformatics and Computational Biology; Vol. 3).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - On the complexity of finding control strategies for Boolean networks

AU - Akutsu, Tatsuya

AU - Hayashida, Morihiro

AU - Ching, Wai Ki

AU - Ng, Kwok Po

PY - 2006

Y1 - 2006

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

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

UR - http://www.scopus.com/inward/record.url?scp=84856983892&partnerID=8YFLogxK

M3 - Conference proceeding

AN - SCOPUS:84856983892

SN - 1860946232

SN - 9781860946233

T3 - Series on Advances in Bioinformatics and Computational Biology

SP - 99

EP - 108

BT - Proceedings of the 4th Asia-Pacific Bioinformatics Conference, APBC 2006

T2 - 4th Asia-Pacific Bioinformatics Conference, APBC 2006

Y2 - 13 February 2006 through 16 February 2006

ER -

On the complexity of finding control strategies for Boolean networks

Abstract

Publication series

Conference

Scopus Subject Areas

Other files and links

Fingerprint

Cite this