A SAT-based Method for Counting All Singleton Attractors in Boolean Networks
A SAT-based Method for Counting All Singleton Attractors in Boolean Networks
Rei Higuchi, Takehide Soh , Daniel Le Berre, Morgan Magnin , Mutsunori Banbara , Naoyuki Tamura
Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 2601-2609.
https://doi.org/10.24963/ijcai.2025/290
Boolean networks (BNs) are widely used to model biological regulatory networks. Attractors here hold significant meaning as they represent long-term behaviors such as homeostasis and the results of cell differentiation. As such, computing attractors is of critical importance to guarantee the validity of a model or to assess its stability and robustness. However, this problem is quite challenging when it comes to large real-world models. To overcome the limits of state-of-the-art BDD-based or ASP-based enumeration approaches, we introduce a SAT-based approach to compute fixed points (singleton attractors) of BN and exhibit its merits for counting the number of singleton attractors of large-scale benchmarks well established in the literature.
Keywords:
Constraint Satisfaction and Optimization: CSO: Applications
Constraint Satisfaction and Optimization: CSO: Modeling
Constraint Satisfaction and Optimization: CSO: Satisfiabilty
Constraint Satisfaction and Optimization: CSO: Solvers and tools
