Analyses and algorithms for predecessor and control problems for boolean networks of bounded indegree

Tatsuya Akutsu*, Morihiro Hayashida, Shu Qin Zhang, Wai Ki Ching, Michael K. Ng

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

3 Citations (Scopus)

Abstract

We study the predecessor and control problems for Boolean networks (BNs). The predecessor problem is to determine whether there exists a global state that transits to a given global state in a given BN, and the control problem is to find a sequence of 0-1 vectors for control nodes in a given BN which leads the BN to a desired global state. The predecessor problem is useful both for the control problem for BNs and for analysis of landscape of basins of attractions in BNs. In this paper, we focus on BNs of bounded indegree and show some hardness results on the computational complexity of the predecessor and control problems. We also present simple algorithms for the predecessor problem that are much faster than the naive exhaustive search-based algorithm. Furthermore, we show some results on distribution of predecessors, which leads to an improved algorithm for the control problem for BNs of bounded indegree.

Original languageEnglish
Pages (from-to)23-34
Number of pages12
JournalIPSJ Transactions on Bioinformatics
Volume1
DOIs
Publication statusPublished - Nov 2008

Scopus Subject Areas

  • Biochemistry, Genetics and Molecular Biology (miscellaneous)
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Analyses and algorithms for predecessor and control problems for boolean networks of bounded indegree'. Together they form a unique fingerprint.

Cite this