Computer Science Department
School of Computer Science, Carnegie Mellon University


Symbolic Approaches for Finding
Control Strategies in Boolean Networks

Christopher James Langmead*, Sumit Kumar Jha

October 2007

This report supercedes
Computer Science Technical Report CMU-CS-07-155


Keywords: Systems biology, model checking, control, Boolean networks

We present an exact algorithm, based on techniques from the field of Model Checking, for finding control policies for Boolean networks (BN) with control nodes. Given a BN, a set of starting states, I, a set of goal states, F, and a target time, t, our algorithm automatically finds a sequence of control signals that deterministically drives the BN from I to F at, or before time t, or else guarantees that no such policy exists. Despite recent hardness-results for finding control policies for BNs, we show that, in practice, our algorithm runs in seconds to minutes on over 13,400 BNs of varying sizes and topologies, including a BN model of embryogenesis in D. melanogaster with 15,360 Boolean variables. We then extend our method to automatically identify a set of Boolean transfer functions that reproduce the qualitative behavior of gene regulatory networks. Specifically, we automatically (re)learn a BN model of D. melanogaster embryogenesis in 5.3 seconds, from a space containing 6.9 x 1010 possible models.

19 pages

*Department of Computer Science and Department of Biological Sciences, Carnegie Mellon University

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by