title: Symbolic approaches for finding control strategies in Boolean Networks.
abstract: 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 Drosophila 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 learn a BN model of D. melanogaster embryogenesis in 5.3 seconds, from a space containing 6.9 x 10(10) possible models.
authors.affiliation: Department of Computer Science and the Lane Centre for Computational Biology, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA. cjl@cs.cmu.edu
authors.forename: Christopher James
authors.initials: CJ
authors.lastname: Langmead
authors.forename: Sumit Kumar
authors.initials: SK
authors.lastname: Jha