IEICE TRANSACTIONS on Fundamentals
Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
Summary :
The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor, which is also called a fixed point, is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in O(n 2n) time, no O((2-ε)n) (ε > 0) time algorithm was known even for an AND/OR BN with non-restricted indegree, where n is the number of nodes in a BN. In this paper, we present an O(1.787n) time algorithm for detecting a singleton attractor of a given AND/OR BN, along with related results. We also show that detection of a singleton attractor in a BN with maximum indegree two is NP-hard and can be polynomially reduced to a satisfiability problem.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.2 pp.493-501
- Publication Date
- 2009/02/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E92.A.493
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
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
Takeyuki TAMURA, Tatsuya AKUTSU, "Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 2, pp. 493-501, February 2009, doi: 10.1587/transfun.E92.A.493.
Abstract: The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor, which is also called a fixed point, is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in O(n 2n) time, no O((2-ε)n) (ε > 0) time algorithm was known even for an AND/OR BN with non-restricted indegree, where n is the number of nodes in a BN. In this paper, we present an O(1.787n) time algorithm for detecting a singleton attractor of a given AND/OR BN, along with related results. We also show that detection of a singleton attractor in a BN with maximum indegree two is NP-hard and can be polynomially reduced to a satisfiability problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.493/_p
Copy
@ARTICLE{e92-a_2_493,
author={Takeyuki TAMURA, Tatsuya AKUTSU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms},
year={2009},
volume={E92-A},
number={2},
pages={493-501},
abstract={The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor, which is also called a fixed point, is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in O(n 2n) time, no O((2-ε)n) (ε > 0) time algorithm was known even for an AND/OR BN with non-restricted indegree, where n is the number of nodes in a BN. In this paper, we present an O(1.787n) time algorithm for detecting a singleton attractor of a given AND/OR BN, along with related results. We also show that detection of a singleton attractor in a BN with maximum indegree two is NP-hard and can be polynomially reduced to a satisfiability problem.},
keywords={},
doi={10.1587/transfun.E92.A.493},
ISSN={1745-1337},
month={February},}
Copy
TY - JOUR
TI - Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 493
EP - 501
AU - Takeyuki TAMURA
AU - Tatsuya AKUTSU
PY - 2009
DO - 10.1587/transfun.E92.A.493
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2009
AB - The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor, which is also called a fixed point, is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in O(n 2n) time, no O((2-ε)n) (ε > 0) time algorithm was known even for an AND/OR BN with non-restricted indegree, where n is the number of nodes in a BN. In this paper, we present an O(1.787n) time algorithm for detecting a singleton attractor of a given AND/OR BN, along with related results. We also show that detection of a singleton attractor in a BN with maximum indegree two is NP-hard and can be polynomially reduced to a satisfiability problem.
ER -
English
