Analysis and Control of Deterministic and Probabilistic Boolean Networks

Tatsuya Akutsu
Bioinformatics Center
Institute for Chemical Research
Kyoto University

Analysis of genetic networks is an important topic in computational systems biology. For that purpose, various mathematical models of genetic networks have been proposed and utilized. In this talk, we focus on the Boolean network (BN) and the probabilistic Boolean network (PBN), where PBN is a probabilistic extension of BN. Furthermore, we focus on computational aspects of detection/enumeration of steady-states and finding of control actions for both BNs and PBNs. We give a brief introduction of these models and review works (with focusing on our works) on the following problems, BN-ATTRACTOR: given a BN, identify all singleton attractors and cyclic attractors with short period, BN-CONTROL: given a BN, an initial state and a desired state, find a control sequence of external nodes leading to the desired state, PBN-STEADY: given a PBN, find the steady-state distribution, PBN-CONTROL: given a PBN along with cost function and its initial state, find a sequence of control actions with the minimum cost. We show that all of these problems are NP-hard. For BN-ATTRACTOR, we present several algorithms that are much efficient than the naive algorithm. For BN-CONTROL, we present some polynomial time algorithm for a special case. For PBN-STEADY, we present some matrix-based methods. For PBN-CONTROL, we briefly review dynamic programming algorithms developed by Dougherty et al. Finally, we discuss possible future developments on these problems.

Webmaster: Takehide Soh (E-mail soh at nii.ac.jp)
Last modified: 19th Aug 2008