Tackling Universal Properties of Minimal Trap Spaces of Boolean Networks
This work tackles computational challenges in analyzing Boolean networks for systems biology, offering incremental improvements in solving complex logical problems related to network dynamics.
The paper addresses the logical reasoning on universal properties of minimal trap spaces (MTSs) in Boolean networks, focusing on reprogramming and synthesis problems, and reduces them to solving quantified propositional logic formulas with three quantifiers. It introduces a Counter-Example Guided Refinement Abstraction (CEGAR) method, coupled with Answer-Set Programming, and demonstrates tractability on biological network models.
Minimal trap spaces (MTSs) capture subspaces in which the Boolean dynamics is trapped, whatever the update mode. They correspond to the attractors of the most permissive mode. Due to their versatility, the computation of MTSs has recently gained traction, essentially by focusing on their enumeration. In this paper, we address the logical reasoning on universal properties of MTSs in the scope of two problems: the reprogramming of Boolean networks for identifying the permanent freeze of Boolean variables that enforce a given property on all the MTSs, and the synthesis of Boolean networks from universal properties on their MTSs. Both problems reduce to solving the satisfiability of quantified propositional logic formula with 3 levels of quantifiers ($\exists\forall\exists$). In this paper, we introduce a Counter-Example Guided Refinement Abstraction (CEGAR) to efficiently solve these problems by coupling the resolution of two simpler formulas. We provide a prototype relying on Answer-Set Programming for each formula and show its tractability on a wide range of Boolean models of biological networks.