Tackling universal properties of minimal trap spaces of Boolean networks

DOI10.1007/978-3-031-42697-1_11MaRDI QIDQ6199824zbMATH OpenOpenAlexFDO

Authors Sara Riva, Jean-Marie Lagniez, Gustavo Magaña López, Loïc Paulevé

Publication date 28 February 2024

Published in Computational Methods in Systems Biology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.02442

zbMATH Keywords

attractorsBoolean networksCEGARQBFsynthesis

Mathematics Subject Classification ID

Systems biology, networks (92C42)

Abstract: 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 ($existsforallexists$). 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.

Recommendations

• Minimal trap spaces of logical models are maximal siphons of their Petri net encoding
• Computing maximal and minimal trap spaces of Boolean networks
• Control strategy identification via trap spaces in Boolean networks
• Relationship between the reprogramming determinants of Boolean networks and their interaction graph
• Sequential reprogramming of Boolean networks made practical

Cites work

• AEON: attractor bifurcation analysis of parametrised Boolean networks
• Bilevel integer programming on a Boolean network for discovering critical genetic alterations in cancer development and therapy
• Counterexample-guided abstraction refinement for symbolic model checking
• DepQBF 6.0: a search-based QBF solver beyond traditional QCDCL
• Handbook of satisfiability. In 2 parts
• Knowledge compilation with empowerment
• Knowledge Representation, Reasoning and Declarative Problem Solving
• Maximum number of fixed points in regulatory Boolean networks
• Minimal trap spaces of logical models are maximal siphons of their Petri net encoding
• Multi-shot ASP solving with clingo
• Nested Boolean functions as models for quantified Boolean formulas
• Prioritization of candidate genes through Boolean networks
• Synthesis and simulation of ensembles of Boolean networks for cell fate decision

Cited in

(1)

• Computational complexity of minimal trap spaces in Boolean networks

This page was built for publication: Tackling universal properties of minimal trap spaces of Boolean networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199824)