Research map / Probabilistic and scientific modeling / Molecules and proteins
Scalable Enumeration of Trap Spaces in Boolean Networks via Answer Set Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes tsconj, an answer set programming encoding over negative normal forms (with BDD fallback for unsafe formulas) that enumerates minimal and maximal trap spaces of Boolean networks faster and at larger scale than pyboolnet, mpbn, trappist and trapmvn.
Problem
Enumerating trap spaces (minimal and maximal hypercubes that cannot be escaped) in Boolean networks is computationally expensive and existing tools do not scale to large, complex models because they need costly intermediate representations such as prime implicants, DNFs, BDDs or Petri nets.
Approach
Encode trap-space conditions as an ASP program built from negative normal forms of each node's update function (with a BDD-derived DNF only when a formula is unsafe), using variable-free atoms and no choice rules for minimal trap spaces, and use subset-maximality solving for maximal trap spaces.
Key results
- On the 400 random models, tsconj completed all 400 within 1 minute, while trapmvn completed 34 and trappist 4 in the same limit.
- On the Very Large Boolean Networks dataset (up to 100,000 variables), tsconj completed all 28 within 1 hour, versus 20 for trapmvn and 18 for mpbn.
- On the Biodivine Boolean Models, tsconj completed 212/212 within 1 hour, matching the best tools and outperforming pyboolnet (203/212).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use tsconj instead of trapmvn | minimal trap space enumeration · Biodivine Boolean Models | models completed within 1h: 211/212 -> 212/212 | Helped |
| use tsconj instead of trapmvn | minimal trap space enumeration · Very Large Boolean Networks | models completed within 1h: 20/28 -> 28/28 | Helped |
| use tsconj instead of mpbn | minimal trap space enumeration · Manually generated models | models completed within 1min: 303/400 -> 400/400 | Helped |
Surprising findings
- Using choice rules and disjunctive rules is a source of inefficiency for ASP solvers, yet the proposed method still outperforms methods that avoid them in the maximal case.
- trapmvn's heuristic improvements over trappist give large gains on random models but not on real-world models, where they are largely comparable.
Limitations
- Some hard models still cannot be handled by any tool; unsafe formulas require BDD construction, which can be expensive.
- The safeness condition is conservative and may classify simple formulas as unsafe.
- Evaluation focuses on time to first minimal trap space; maximal trap space results are only in supplementary material.
Experimental setup
Datasets: Biodivine Boolean Models (212 real-world BNs) manually selected real-world models (39) Very Large Boolean Networks (28 random BNs) random BNs from Benes et al. 2021 generator (400)
Benchmarks: Biodivine Boolean Models manually selected real-world models Very Large Boolean Networks 400 random Boolean networks (1000-5000 variables)
Metrics: number of models completed within time limits (<1s, <1min, < runtime to first minimal trap space speed-up ratio vs other tools
Baselines: pyboolnet mpbn trappist trapmvn
Builds on: Klarner et al. 2015 ASP trap space enumeration mpbn locally-monotonic encoding trappist Petri net siphon method clingo
Closest papers by meaning
- Engineering an Exact Pseudo-Boolean Model Counter (AAAI 2024 · similarity 0.84)
- CEGAR-Based Approach for Solving Combinatorial Optimization Modulo Quantified Linear Arithmetics Problems (AAAI 2024 · similarity 0.84)
- On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? (AAAI 2024 · similarity 0.83)
- Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates (NeurIPS 2025 · similarity 0.83)
- A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.83)
- Cirbo: A New Tool for Boolean Circuit Analysis and Synthesis (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.