A SAT-based Method for Counting All Singleton Attractors in Boolean Networks

Higuchi, Rei; Soh, Takehide; Le Berre, Daniel; Magnin, Morgan; Banbara, Mutsunori; Tamura, Naoyuki

doi:10.24963/ijcai.2025/290

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

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 2601-2609.

https://doi.org/10.24963/ijcai.2025/290

Keywords

Constraint Satisfaction and Optimization: CSO: Modeling
Constraint Satisfaction and Optimization: CSO: Satisfiabilty
Constraint Satisfaction and Optimization: CSO: Applications
Constraint Satisfaction and Optimization: CSO: Solvers and tools

Abstract

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.

Rei Higuchi, Takehide Soh, Daniel Le Berre, Morgan Magnin, Mutsunori Banbara, and Naoyuki Tamura. 2025. A SAT-based Method for Counting All Singleton Attractors in Boolean Networks. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 2601–2609. https://doi.org/10.24963/ijcai.2025/290

@inproceedings{ijcai2025p290,
  title     = {A SAT-based Method for Counting All Singleton Attractors in Boolean Networks},
  author    = {Higuchi, Rei and Soh, Takehide and Le Berre, Daniel and Magnin, Morgan and Banbara, Mutsunori and Tamura, Naoyuki},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {2601--2609},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/290},
  url       = {https://doi.org/10.24963/ijcai.2025/290},
}

TY  - CPAPER
TI  - A SAT-based Method for Counting All Singleton Attractors in Boolean Networks
AU  - Higuchi, Rei
AU  - Soh, Takehide
AU  - Le Berre, Daniel
AU  - Magnin, Morgan
AU  - Banbara, Mutsunori
AU  - Tamura, Naoyuki
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 2601
EP  - 2609
DO  - 10.24963/ijcai.2025/290
UR  - https://doi.org/10.24963/ijcai.2025/290
ER  -