Scalable Enumeration of Trap Spaces in Boolean Networks via Answer Set Programming

Giang V. Trinh, Belaid Benhamou, Samuel Pastva, Sylvain SolimanAAAI 2024 · DOI

Abstract

Analyzing the long-term behavior of complex biological systems modeled as Boolean Networks (BNs) is a fundamental challenge in systems biology. While attractors represent stable phenotypes, their exact computation is often intractable for large networks. Trap spaces—hypercubes that trap the system's state—offer a robust approximation. This paper presents tsconj, a highly scalable tool for enumerating trap spaces using Answer Set Programming (ASP). By employing a novel logic encoding based on Negative Normal Forms (NNF) and a "safeness" condition, tsconj avoids the exponential bottlenecks of traditional methods. Benchmarks show that tsconj can analyze networks with up to 100,000 nodes, outperforming existing state-of-the-art tools by orders of magnitude.

Introduction

Boolean Networks (BNs) are widely used to model gene regulatory networks and signaling pathways. A primary goal in BN analysis is identifying attractors, which correspond to steady-state biological behaviors. However, finding attractors in large-scale models is computationally expensive. Trap spaces serve as a practical alternative; minimal trap spaces are particularly useful as they often contain one or more attractors.

The current bottleneck in trap space enumeration lies in the intermediate representations used by existing tools, such as prime implicants or Disjunctive Normal Forms (DNFs). For complex biological functions, these representations can grow exponentially, leading to memory exhaustion or timeouts.

Methodology: The tsconj Approach

The authors propose tsconj, which leverages the declarative power of Answer Set Programming (ASP) to solve the trap space enumeration problem efficiently.

Negative Normal Form (NNF) Encoding

Unlike previous methods that require expensive pre-computation of DNFs, tsconj utilizes Negative Normal Forms. NNFs are syntactically easy to obtain by recursively applying De Morgan’s laws. This shift from semantic minimality (prime implicants) to syntactic efficiency (NNF) is a core innovation of the tool.

The Safeness Condition and Hybrid BDDs

The tool introduces a "safeness" property for Boolean formulas. Safe formulas can be directly translated into ASP rules. For "unsafe" formulas, tsconj falls back to using Binary Decision Diagrams (BDDs) to generate a safe DNF. Since most biological functions are relatively simple, this fallback is rarely needed, significantly reducing computational overhead.

Experimental Evaluation

The performance of tsconj was evaluated against four diverse datasets, including real-world biological models and synthetic networks with up to 100,000 variables.

Key Results

tsconj demonstrated superior performance across all benchmarks. On the 400 random models, it was the only tool to complete all instances, while the baseline pyboolnet failed on all of them.

Cumulative distribution of completed instances over runtime for the 400 random models, showing tsconj (dark green) outperforming competitors.

As shown in the runtime analysis, tsconj consistently reaches the completion threshold faster than competing tools like trapmvn and mpbn. In many cases, it achieved speedups ranging from 16x to 64x.

Comprehensive benchmark results across four datasets, showing the number of instances solved within specific time limits.

The scalability of tsconj is most evident in the Very Large Boolean Networks (VLBN) dataset, where it successfully processed networks with 100,000 nodes—a feat unattainable by other state-of-the-art tools. It was also the only method to solve every model in the Biodivine Boolean Models (BBM) dataset within a one-hour limit.

Conclusion

tsconj represents a significant advancement in the analysis of large-scale Boolean Networks. By replacing traditional DNF-based approaches with an efficient ASP-NNF encoding, it enables the study of biological models that were previously computationally inaccessible. Future work will focus on refining the safeness condition and exploring alternative logic solvers to further push the boundaries of network scalability.

Summary updated

BibTeX
@inproceedings{trinh2024scalable,
  author = {Giang V. Trinh and Belaid Benhamou and Samuel Pastva and Sylvain Soliman},
  title = {{Scalable Enumeration of Trap Spaces in Boolean Networks via Answer Set Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28943},
}

Loading related content...

Figure