Computer Science Department
School of Computer Science, Carnegie Mellon University
Symbolic Approaches for Finding
Christopher James Langmead*, Sumit Kumar Jha
This report supercedes
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.
*Department of Computer Science and Department of Biological Sciences, Carnegie Mellon University