IEICE TRANSACTIONS on Fundamentals
A Fixed-Parameter Algorithm for Detecting a Singleton Attractor in an AND/OR Boolean Network with Bounded Treewidth
Summary :
The Boolean network can be used as a mathematical model for gene regulatory networks. An attractor, which is a state of a Boolean network repeating itself periodically, can represent a stable stage of a gene regulatory network. It is known that the problem of finding an attractor of the shortest period is NP-hard. In this article, we give a fixed-parameter algorithm for detecting a singleton attractor (SA) for a Boolean network that has only AND and OR Boolean functions of literals and has bounded treewidth k. The algorithm is further extended to detect an SA for a constant-depth nested canalyzing Boolean network with bounded treewidth. We also prove the fixed-parameter intractability of the detection of an SA for a general Boolean network with bounded treewidth.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.1 pp.384-390
- Publication Date
- 2015/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E98.A.384
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Chia-Jung CHANG
National Taiwan University
Takeyuki TAMURA
Kyoto University
Kun-Mao CHAO
National Taiwan University
Tatsuya AKUTSU
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Chia-Jung CHANG, Takeyuki TAMURA, Kun-Mao CHAO, Tatsuya AKUTSU, "A Fixed-Parameter Algorithm for Detecting a Singleton Attractor in an AND/OR Boolean Network with Bounded Treewidth" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 1, pp. 384-390, January 2015, doi: 10.1587/transfun.E98.A.384.
Abstract: The Boolean network can be used as a mathematical model for gene regulatory networks. An attractor, which is a state of a Boolean network repeating itself periodically, can represent a stable stage of a gene regulatory network. It is known that the problem of finding an attractor of the shortest period is NP-hard. In this article, we give a fixed-parameter algorithm for detecting a singleton attractor (SA) for a Boolean network that has only AND and OR Boolean functions of literals and has bounded treewidth k. The algorithm is further extended to detect an SA for a constant-depth nested canalyzing Boolean network with bounded treewidth. We also prove the fixed-parameter intractability of the detection of an SA for a general Boolean network with bounded treewidth.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.384/_p
Copy
@ARTICLE{e98-a_1_384,
author={Chia-Jung CHANG, Takeyuki TAMURA, Kun-Mao CHAO, Tatsuya AKUTSU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fixed-Parameter Algorithm for Detecting a Singleton Attractor in an AND/OR Boolean Network with Bounded Treewidth},
year={2015},
volume={E98-A},
number={1},
pages={384-390},
abstract={The Boolean network can be used as a mathematical model for gene regulatory networks. An attractor, which is a state of a Boolean network repeating itself periodically, can represent a stable stage of a gene regulatory network. It is known that the problem of finding an attractor of the shortest period is NP-hard. In this article, we give a fixed-parameter algorithm for detecting a singleton attractor (SA) for a Boolean network that has only AND and OR Boolean functions of literals and has bounded treewidth k. The algorithm is further extended to detect an SA for a constant-depth nested canalyzing Boolean network with bounded treewidth. We also prove the fixed-parameter intractability of the detection of an SA for a general Boolean network with bounded treewidth.},
keywords={},
doi={10.1587/transfun.E98.A.384},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - A Fixed-Parameter Algorithm for Detecting a Singleton Attractor in an AND/OR Boolean Network with Bounded Treewidth
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 384
EP - 390
AU - Chia-Jung CHANG
AU - Takeyuki TAMURA
AU - Kun-Mao CHAO
AU - Tatsuya AKUTSU
PY - 2015
DO - 10.1587/transfun.E98.A.384
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2015
AB - The Boolean network can be used as a mathematical model for gene regulatory networks. An attractor, which is a state of a Boolean network repeating itself periodically, can represent a stable stage of a gene regulatory network. It is known that the problem of finding an attractor of the shortest period is NP-hard. In this article, we give a fixed-parameter algorithm for detecting a singleton attractor (SA) for a Boolean network that has only AND and OR Boolean functions of literals and has bounded treewidth k. The algorithm is further extended to detect an SA for a constant-depth nested canalyzing Boolean network with bounded treewidth. We also prove the fixed-parameter intractability of the detection of an SA for a general Boolean network with bounded treewidth.
ER -
English
