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.
- 一般社団法人情報処理学会の論文
- 2008-11-28
著者
-
Tatsuya Akutsu
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
Morihiro Hayashida
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Tatsuya Akutsu
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
- RNA-RNA Interaction Prediction Using Integer Programming with Threshold Cut
- A Quadsection Algorithm for Grammar-Based Image Compression
- Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
- Conditional Random Field Approach to Prediction of Protein-protein Interactions Using Domain Information
- Integer Programming and Dynamic Programming-based Methods of Optimizing Control Policy in Probabilistic Boolean Networks with Hard Constraints
- An Improved Clique-Based Method for Computing Edit Distance between Rooted Unordered Trees
- Prediction of protein residue contacts using discriminative random field
- Prediction of protein residue contacts using discriminative random field