Generalizing Gillespie’s Direct Method to Enable Network-Free Simulations

Ryan Suderman, Eshan D. Mitra, Yen Ting Lin, Keesha E. Erickson, Song Feng, William S. HlavacekBulletin 2018 · DOI · arXiv

Introduction

In systems biology, modeling the intricate dance of protein interactions within a cell is a monumental challenge. Traditional approaches, such as Ordinary Differential Equations (ODEs) or the classic Stochastic Simulation Algorithm (SSA), rely on tracking the concentrations of specific molecular "species." However, biological molecules are inherently complex; a single protein may possess numerous modification sites, such as phosphorylation sites.

This complexity leads to a combinatorial explosion. For instance, the Platelet-Derived Growth Factor Receptor (PDGFR) has ten phosphorylation sites. If each site can exist in a binary state (on or off), a single receptor has $2^{10} = 1,024$ possible states. When these receptors dimerize, the number of potential biochemical states exceeds 500,000. Traditional "network-based" methods require an explicit equation for every possible state and reaction, making the simulation of many biological systems computationally intractable. This paper explores a transition to "network-free" simulation to bypass this bottleneck.

Rule-Based Foundations

The core innovation of network-free simulation is Rule-Based Modeling. Instead of defining reactions between every possible specific species, researchers define rules based on molecular patterns. A rule specifies the necessary context for a reaction to occur—the "reaction center"—while ignoring irrelevant details of the molecule's state.

Core components of rule-based modeling: molecule types, site specification hierarchies, pattern matching, and reaction rules.

As shown in the figure above, molecules are treated as agents with internal sites. Patterns allow the system to identify sets of molecules that satisfy specific conditions, regardless of their full specification. This "context independence" allows a handful of rules to represent hundreds of thousands of potential reactions.

The Generalized Gillespie Algorithm

To execute these models, the authors generalize Gillespie’s direct method into a network-free engine. Rather than calculating rates based on global species concentrations, the engine maintains match lists that track which molecules currently satisfy the patterns defined in the rules.

The generalized Gillespie simulation loop, showing the iterative process of sampling waiting times and rules based on match lists.

The simulation follows an iterative loop:

  1. Initialization: The system is populated with individual molecule objects.
  2. Rate Calculation: The engine counts how many ways rule patterns match the current molecular mixture.
  3. Sampling: A Monte Carlo approach determines the time until the next event ($\Delta t$) and selects which rule fires.
  4. Updating: After a reaction, the system performs incremental updates—removing matches that are no longer valid and identifying new matches created by the state change.

Applications and Insights

The framework has been validated against several landmark biological models, including PDGFR activation and DNA Base Excision Repair. A key insight from these simulations is the phenomenon of clonal divergence. Because the state space is so vast, two genetically identical cells starting in the same state will diverge into unique biochemical configurations within minutes. Despite this stochasticity, biological signaling remains robust.

Furthermore, the algorithm handles large molecular aggregates through "null events." If a sampled reaction is mathematically valid but physically impossible (e.g., binding two sites already in the same complex), the simulator advances time without changing the state, maintaining mathematical rigor without crashing.

Conclusion and Future Work

Network-free simulation enables the exact simulation of systems with astronomical state spaces. By using incremental updates, the computational cost scales with the number of molecules and rules rather than the number of possible species. While highly efficient for complex systems, the method faces challenges in high-population systems of simple molecules where tracking individual agents adds overhead. Future frontiers include addressing the "gel problem"—where frequent null events in aggregates slow simulation—and integrating 3D spatial dynamics into the well-mixed models currently supported by engines like NFsim and KaSim.

Summary updated

BibTeX
@article{suderman2018generalizing,
  author = {Ryan Suderman and Eshan D. Mitra and Yen Ting Lin and Keesha E. Erickson and Song Feng and William S. Hlavacek},
  title = {{Generalizing Gillespie’s Direct Method to Enable Network-Free Simulations}},
  journal = {Bulletin},
  year = {2018},
  doi = {10.1007/s11538-018-0418-2},
}
Figure