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

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.

Authors

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

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