Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
スポンサーリンク
概要
- 論文の詳細を見る
We study the predecessor and control problems for Boolean networks (BNs). The predecessor problem is to determine whether there exists a global state that transits to a given global state in a given BN, and the control problem is to find a sequence of 0-1 vectors for control nodes in a given BN which leads the BN to a desired global state. The predecessor problem is useful both for the control problem for BNs and for analysis of landscape of basins of attractions in BNs. In this paper, we focus on BNs of bounded indegree and show some hardness results on the computational complexity of the predecessor and control problems. We also present simple algorithms for the predecessor problem that are much faster than the naive exhaustive search-based algorithm. Furthermore, we show some results on distribution of predecessors, which leads to an improved algorithm for the control problem for BNs of bounded indegree.
著者
-
Ching Wai-ki
Department Of Mathematics The University Of Hong Kong
-
Hayashida Morihiro
Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.
-
Akutsu Tatsuya
Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.
-
CHING Wai-Ki
Department of Mathematics, The University of Hong Kong
-
Zhang Shu-Qin
School of Mathematical Sciences, Fudan University
-
Ng Michael
Department of Mathematics, Hong Kong Baptist University
関連論文
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- 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)
- Integer Programming and Dynamic Programming-based Methods of Optimizing Control Policy in Probabilistic Boolean Networks with Hard Constraints
- Hardness Results on Local Multiple Alignment of Biological Sequences
- 1P-279 酸化ストレス下におけるアポトーシス制御機構の数理的解明(放射線生物/活性酸素,第46回日本生物物理学会年会)
- Efficient Computation of Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
- 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