Model checking the evolution of gene regulatory networks

Mirco Giacobbe, Calin C. Guet, Ashutosh Gupta, Thomas A. Henzinger, Tiago Paixão, Tatjana Petrov

Introduction

Understanding how gene regulatory networks (GRNs) evolve while maintaining their core biological functions is a fundamental challenge in evolutionary biology. Traditional methods rely heavily on stochastic simulations, which can be computationally prohibitive and lack formal guarantees. This research, published in Acta Informatica, introduces a formal verification framework that replaces slow simulation-based testing with exact parameter synthesis, enabling a more precise and efficient analysis of biological robustness.

The Challenge of Mutational Robustness

In the widely used Wagner’s model, GRNs are represented as discrete systems where genes act as binary switches. The state of each gene is determined by the weighted influence of other genes in the network. A key metric in this field is mutational robustness: the probability that a network will retain its functional properties (such as reaching a specific steady state or exhibiting oscillatory behavior) after a mutation alters its connection weights.

Historically, researchers have estimated robustness by simulating millions of random mutants—a "brute force" approach that struggles to scale as network complexity increases.

Formal Verification Methodology

The authors propose a shift from sampling-based simulation to symbolic bounded model checking (BMC). The process begins by formally defining desired biological behaviors using Linear Temporal Logic (LTL). For example, bistability or clock-like oscillations are encoded as temporal properties.

Instead of testing individual networks, the weights are treated as symbolic variables. The network's transitions and the LTL properties are encoded into a logic formula. Using the Z3 SMT solver, the researchers synthesize the set of all weight values that satisfy the functional requirements. These constraints are then represented using Linear Decision Diagrams (LDDs), which allow for near-instantaneous evaluation of whether a specific mutant is robust.

Figure 1: (a) A two-gene regulatory network model with weights (w) and thresholds (t). (b) The corresponding state transition graph based on logic conditions.

Results and Scalability

The method was benchmarked against eight GRN topologies, including bistable networks and repressilators of various sizes. The results demonstrate significant performance gains:

  • Speedup: In 75% of the tested networks, the constraint-based approach outperformed traditional simulation. For the misa network, the evaluation of synthesized constraints was significantly faster than re-running simulations for each sample.
  • Scalability: The approach successfully handled an osc25 network (25 genes), synthesizing constraints in just 3.5 seconds—a task that would be virtually impossible for exhaustive simulation given the $2^{25}$ possible initial states.
  • Precision: The efficiency of LDD evaluation allowed the authors to perform up to $10^7$ samples, achieving extremely tight confidence intervals for robustness metrics.
Figure 2: Performance comparison for the misa network, showing that evaluating synthesized constraints (evaluation) scales better than full execution (execution) as the number of samples increases.

Conclusion and Future Directions

By bridging formal logic and population genetics, this work provides a rigorous mathematical foundation for studying evolution. The authors demonstrate that long-term robustness under selection can be calculated using the eigenvalues of mutation transition matrices derived from their synthesized constraints.

While the method faces challenges with highly connected networks where constraint complexity grows, it offers a powerful alternative to simulation for many biological models. Future work aims to extend this framework to continuous stochastic models and to use point-counting algorithms for exact, non-statistical robustness calculations.

Summary updated

Abstract

The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs—an important problem of interest in evolutionary biology—more efficiently than the classical simulation method. We specify the property in linear temporal logic. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.
BibTeX
@article{giacobbe2017model,
  author = {Mirco Giacobbe and Calin C. Guet and Ashutosh Gupta and Thomas A. Henzinger and Tiago Paixão and Tatjana Petrov},
  title = {{Model checking the evolution of gene regulatory networks}},
  journal = {Acta Informatica},
  year = {2017},
  doi = {10.1007/s00236-016-0278-x},
}
Figure