On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• （社）電子情報通信学会の論文

著者

• Akutsu Tatsuya

  Kyoto Univ. Kyoto‐shi Jpn

• Akutsu Tatsuya

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• TAMURA Takeyuki

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

関連論文

• Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
• Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
• On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
• Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences(Discrete Mathematics and Its Applications)
• A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
• Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints(Discrete Mathematics and Its Applications)
• Inferring pedigree graphs from genetic distances
• On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
• Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics

スポンサーリンク