Abstract
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.
Last modified: 19th Aug 2008