The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Encontrar pontos fixos em sistemas dinâmicos discretos é importante porque os pontos fixos correspondem a estados estacionários. A rede booleana é considerada um dos sistemas dinâmicos discretos mais simples e é frequentemente usada como modelo de redes genéticas. Sabe-se que a detecção de um ponto fixo em uma rede booleana com n nós e grau máximo K pode ser transformado polinomialmente em (K+1)-SAT com n variáveis. Neste artigo, nos concentramos no caso de K=2 e apresente um O(1.3171n) algoritmo de tempo esperado, que é mais rápido que o algoritmo ingênuo baseado em uma redução para 3-SAT, onde assumimos que os nós com grau 2 não contêm auto-loops. Também mostramos um algoritmo para o caso geral de K=2 que é um pouco mais rápido que o algoritmo ingênuo.
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.
Copiar
Tatsuya AKUTSU, Takeyuki TAMURA, "On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 8, pp. 1771-1778, August 2009, doi: 10.1587/transfun.E92.A.1771.
Abstract: Finding fixed points in discrete dynamical systems is important because fixed points correspond to steady-states. The Boolean network is considered as one of the simplest discrete dynamical systems and is often used as a model of genetic networks. It is known that detection of a fixed point in a Boolean network with n nodes and maximum indegree K can be polynomially transformed into (K+1)-SAT with n variables. In this paper, we focus on the case of K=2 and present an O(1.3171n) expected time algorithm, which is faster than the naive algorithm based on a reduction to 3-SAT, where we assume that nodes with indegree 2 do not contain self-loops. We also show an algorithm for the general case of K=2 that is slightly faster than the naive algorithm.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1771/_p
Copiar
@ARTICLE{e92-a_8_1771,
author={Tatsuya AKUTSU, Takeyuki TAMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2},
year={2009},
volume={E92-A},
number={8},
pages={1771-1778},
abstract={Finding fixed points in discrete dynamical systems is important because fixed points correspond to steady-states. The Boolean network is considered as one of the simplest discrete dynamical systems and is often used as a model of genetic networks. It is known that detection of a fixed point in a Boolean network with n nodes and maximum indegree K can be polynomially transformed into (K+1)-SAT with n variables. In this paper, we focus on the case of K=2 and present an O(1.3171n) expected time algorithm, which is faster than the naive algorithm based on a reduction to 3-SAT, where we assume that nodes with indegree 2 do not contain self-loops. We also show an algorithm for the general case of K=2 that is slightly faster than the naive algorithm.},
keywords={},
doi={10.1587/transfun.E92.A.1771},
ISSN={1745-1337},
month={August},}
Copiar
TY - JOUR
TI - On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1771
EP - 1778
AU - Tatsuya AKUTSU
AU - Takeyuki TAMURA
PY - 2009
DO - 10.1587/transfun.E92.A.1771
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2009
AB - Finding fixed points in discrete dynamical systems is important because fixed points correspond to steady-states. The Boolean network is considered as one of the simplest discrete dynamical systems and is often used as a model of genetic networks. It is known that detection of a fixed point in a Boolean network with n nodes and maximum indegree K can be polynomially transformed into (K+1)-SAT with n variables. In this paper, we focus on the case of K=2 and present an O(1.3171n) expected time algorithm, which is faster than the naive algorithm based on a reduction to 3-SAT, where we assume that nodes with indegree 2 do not contain self-loops. We also show an algorithm for the general case of K=2 that is slightly faster than the naive algorithm.
ER -