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.
- （社）電子情報通信学会の論文
- 2009-08-01
著者
-
TAMURA Takeyuki
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
Akutsu Tatsuya
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Tamura Takeyuki
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Akutsu Tatsuya
Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.
関連論文
- 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
- Hardness Results on Local Multiple Alignment of Biological Sequences
- 1P-279 酸化ストレス下におけるアポトーシス制御機構の数理的解明(放射線生物/活性酸素,第46回日本生物物理学会年会)
- Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
- Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks
- On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
- Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Hardness Results on Local Multiple Alignment of Biological Sequences
- Kernel Methods for Chemical Compounds: From Classification to Design
- Conservation Laws and Symmetries in Competitive Systems
- Measuring the Similarity of Protein Structures Using Image Compression Algorithms
- An Efficient Method of Computing Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
- Conservation Laws and Symmetries in Competitive Systems
- Integer Programming-Based Approach to Attractor Detection and Control of Boolean Networks
- On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors