The search functionality is under construction.

The search functionality is under construction.

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* 2^{n}) 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.787^{n}) 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

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.

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* 2^{n}) 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.787^{n}) 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* 2^{n}) 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.787^{n}) 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* 2^{n}) 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.787^{n}) 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 -