Abstract
The Boolean network is a mathematical model of biological systems, and has attracted much attention as a qualitative tool for analyzing the regulatory system. The stable states and dynamics of Boolean networks are characterized by their attractors, whose properties have been analyzed computationally, yet not much work has been done from the viewpoint of logical inference systems. In this paper, we show direct translations of Boolean networks into logic programs, and propose new methods to compute their trajectories and attractors based on inference on such logic programs. In particular, point attractors of both synchronous and asynchronous Boolean networks are characterized as supported models of logic programs so that SAT techniques can be applied to compute them. Investigation of these relationships suggests us to view Boolean networks as logic programs and vice versa.
Introduction
In systems biology, Boolean Networks (BNs) serve as a fundamental qualitative framework for modeling gene and protein regulatory interactions. In these networks, the state of each node (representing a gene or protein) is binary—either "on" (1) or "off" (0). The global behavior of the system is dictated by local update rules, leading to a sequence of states known as a trajectory.
The most critical features of BNs are their attractors: the stable states or cycles toward which the system eventually gravitates. These attractors are biologically significant, often representing specific cell types, physiological states, or processes like apoptosis. However, identifying these attractors in large-scale networks is a computationally intensive task, categorized as NP-hard.
Bridging Biology and Logic Programming
While previous research has utilized Artificial Intelligence techniques like Propositional Satisfiability (SAT) and Answer Set Programming (ASP) to analyze BNs, these approaches typically relied on "meta-level" simulations. This paper proposes a more direct connection: treating the biological network itself as a logic program.
Direct Translation
The author introduces a method to map each regulation rule in a BN directly into a rule in a Normal Logic Program (NLP). By expressing these rules in Disjunctive Normal Form (DNF), the logical structure of gene regulation (e.g., "Gene A is activated if Gene B is present AND Gene C is absent") is preserved within the logic programming syntax.
Semantical Characterization
A key theoretical contribution of this work is the proof that "point attractors" (steady states where the system no longer changes) of a synchronous BN are mathematically equivalent to the supported models of the corresponding logic program. This equivalence bridges the gap between the dynamic behavior of biological systems and the static semantics of logic programming.
Computational Inference via SAT Solvers
By establishing this link, the paper enables the application of powerful SAT solvers to biological problems. Using Clark’s Completion, the logic program is transformed into a set of Boolean equations. This allows researchers to find all stable states of a complex network simultaneously, bypassing the need for exhaustive state-space simulation.
The approach is not limited to synchronous models. By incorporating cardinality constraints, the author demonstrates that point attractors remain consistent across both synchronous and asynchronous modeling paradigms, allowing simpler models to provide insights into more complex, realistic biological systems.
Key Results and Practical Application
The theoretical equivalence is supported by formal proofs (Theorems 3.2, 3.3, and 3.5), establishing that trajectories in BNs correspond to orbits in logic programs. Practically, the efficiency of this method was validated using a 52-node model of the Drosophila melanogaster (fruit fly) regulatory network. Using the MiniSat2 solver, all seven point attractors were identified in less than 0.05 seconds, demonstrating the scalability of the logic-based approach.
Conclusion and Future Directions
This research suggests a "dynamic semantics" for logic programming, where rules are viewed as transition functions rather than static facts. While the current method is highly effective for point attractors, future work will focus on more direct characterizations of cyclic attractors. Additionally, the author proposes extending this framework to stochastic models via Probabilistic Boolean Networks and using Inductive Logic Programming (ILP) to infer missing regulatory links from experimental data.
Summary updated