# Accelerated Stochastic Simulation Algorithms

Stochastic simulations of reaction-diffusion processes are frequently used for the modeling of physical phenomena ranging from biology and social sciences to ecosystems and materials processing. In this work we focus on the stochastic modeling and simulation of spatial dynamics of chemical kinetics intrinsic to physical phenomena ranging from morphogenesis and pedestrian traffic to epitaxial growth and epidemics.

### LeSS – Leaping Stochastic Simulation: R-Leaping and D-Leaping

The time evolution of stochastic systems is modeled using the *Stochastic Simulation Algorithm (SSA).* We have developed several novel algorithms which accelerate these simulations. *R-leaping* [1] accelerates the simulation of these systems by reaction leaps. The algorithm is particularly suitable for systems with disparate reaction rates. *D-leaping* [2] accelerates the handling of reactions with delays for leaping algorithms.

These algorithms have been implemented in the LeSS package, available on our software repository.

### Adaptive Mesh Refinement for Spatial SSA

The SSA has become increasingly important in the analysis of cellular systems in biology, where small molecular populations of species can lead to substantial deviations from deterministic simulations. For spatially inhomogeneous systems, SSA is associated with a high computational cost. To resolve this issue, we are currently extending the R-leaping algorithm for a nonuniform discretization of the domain in the spirit of Adaptive Mesh Reﬁnement [3]. This enables the efficient use of computational elements, since more elements can be placed in areas of the domain that are associated with ﬁne spatial scales.

[Bibtex] [Abstract] [PDF] [DOI]

A novel algorithm is proposed for the acceleration of the exact stochastic simulation algorithm by a predefined number of reaction firings (R-leaping) that may occur across several reaction channels. In the present approach, the numbers of reaction firings are correlated binomial distributions and the sampling procedure is independent of any permutation of the reaction channels. This enables the algorithm to efficiently handle large systems with disparate rates, providing substantial computational savings in certain cases. Several mechanisms for controlling the accuracy and the appearance of negative species are described. The advantages and drawbacks of R-leaping are assessed by simulations on a number of benchmark problems and the results are discussed in comparison with established methods.

```
@article{auger2006a,
author = {Anne Auger and Philippe Chatelain and Petros Koumoutsakos},
doi = {10.1063/1.2218339},
journal = {{J. Chem. Phys.}},
month = {aug},
number = {8},
pages = {084103},
publisher = {{AIP} Publishing},
title = {R-leaping: Accelerating the stochastic simulation algorithm by reaction leaps},
url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/auger2006a.pdf},
volume = {125},
year = {2006}
}
```

[Bibtex] [Abstract] [PDF] [DOI]

We propose a novel, accelerated algorithm for the approximate stochastic simulation of biochemical systems with delays. The present work extends existing accelerated algorithms by distributing, in a time adaptive fashion, the delayed reactions so as to minimize the computational effort while preserving their accuracy. The accuracy of the present algorithm is assessed by comparing its results to those of the corresponding delay differential equations for a representative biochemical system. In addition, the fluctuations produced from the present algorithm are comparable to those from an exact stochastic simulation with delays. The algorithm is used to simulate biochemical systems that model oscillatory gene expression. The results indicate that the present algorithm is competitive with existing works for several benchmark problems while it is orders of magnitude faster for certain systems of biochemical reactions.

```
@article{bayati2009a,
author = {Basil Bayati and Philippe Chatelain and Petros Koumoutsakos},
doi = {10.1016/j.jcp.2009.05.004},
journal = {{J. Comput. Phys.}},
month = {sep},
number = {16},
pages = {5908--5916},
publisher = {Elsevier {BV}},
title = {D-leaping: Accelerating stochastic simulation algorithms for reactions with delays},
url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/bayati2009a.pdf},
volume = {228},
year = {2009}
}
```

[Bibtex] [Abstract] [PDF] [DOI]

Stochastic simulations of reaction{–}diffusion processes are used extensively for the modeling of complex systems in areas ranging from biology and social sciences to ecosystems and materials processing. These processes often exhibit disparate scales that render their simulation prohibitive even for massive computational resources. The problem is resolved by introducing a novel stochastic multiresolution method that enables the efficient simulation of reaction{–}diffusion processes as modeled by many-particle systems. The proposed method quantifies and efficiently handles the associated stiffness in simulating the system dynamics and its computational efficiency and accuracy are demonstrated in simulations of a model problem described by the Fisher{–}Kolmogorov equation. The method is general and can be applied to other many-particle models of physical processes.

```
@article{bayati2008a,
author = {Basil Bayati and Philippe Chatelain and Petros Koumoutsakos},
doi = {10.1039/b810795e},
journal = {{Phys. Chem. Chem. Phys.}},
number = {39},
pages = {5963},
publisher = {Royal Society of Chemistry ({RSC})},
title = {Multiresolution stochastic simulations of reaction{\textendash}diffusion processes},
url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/bayati2008a.pdf},
volume = {10},
year = {2008}
}
```

**People:** Basil Bayati, Diego Rossinelli, Philippe Chatelain

**Funding:** ETH Zürich, SystemsX

### Publications

### 2011

- B. Bayati, P. Chatelain, and P. Koumoutsakos, “Adaptive mesh refinement for stochastic reaction–diffusion processes,” J. Comput. Phys., vol. 230, iss. 1, p. 13–26, 2011.

[BibTeX] [Abstract] [PDF] [DOI]

We present an algorithm for Adaptive Mesh Refinement applied to mesoscopic stochastic simulations of spatially evolving reaction-diffusion processes. The transition rates for the diffusion process are derived on adaptive, locally refined structured meshes. Convergence of the diffusion process is presented and the fluctuations of the stochastic process are verified. Furthermore, a refinement criterion is proposed for the evolution of the adaptive mesh. The method is validated in simulations of reaction-diffusion processes as described by the Fisher-Kolmogorov and Gray-Scott equations.

`@article{bayati2011a, author = {Basil Bayati and Philippe Chatelain and Petros Koumoutsakos}, doi = {10.1016/j.jcp.2010.08.035}, journal = {{J. Comput. Phys.}}, month = {jan}, number = {1}, pages = {13--26}, publisher = {Elsevier {BV}}, title = {Adaptive mesh refinement for stochastic reaction{\textendash}diffusion processes}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/bayati2011a.pdf}, volume = {230}, year = {2011} }`

### 2009

- B. Bayati, P. Chatelain, and P. Koumoutsakos, “D-leaping: accelerating stochastic simulation algorithms for reactions with delays,” J. Comput. Phys., vol. 228, iss. 16, p. 5908–5916, 2009.

[BibTeX] [Abstract] [PDF] [DOI]

We propose a novel, accelerated algorithm for the approximate stochastic simulation of biochemical systems with delays. The present work extends existing accelerated algorithms by distributing, in a time adaptive fashion, the delayed reactions so as to minimize the computational effort while preserving their accuracy. The accuracy of the present algorithm is assessed by comparing its results to those of the corresponding delay differential equations for a representative biochemical system. In addition, the fluctuations produced from the present algorithm are comparable to those from an exact stochastic simulation with delays. The algorithm is used to simulate biochemical systems that model oscillatory gene expression. The results indicate that the present algorithm is competitive with existing works for several benchmark problems while it is orders of magnitude faster for certain systems of biochemical reactions.

`@article{bayati2009a, author = {Basil Bayati and Philippe Chatelain and Petros Koumoutsakos}, doi = {10.1016/j.jcp.2009.05.004}, journal = {{J. Comput. Phys.}}, month = {sep}, number = {16}, pages = {5908--5916}, publisher = {Elsevier {BV}}, title = {D-leaping: Accelerating stochastic simulation algorithms for reactions with delays}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/bayati2009a.pdf}, volume = {228}, year = {2009} }`

### 2008

- B. Bayati, P. Chatelain, and P. Koumoutsakos, “Multiresolution stochastic simulations of reaction–diffusion processes,” Phys. Chem. Chem. Phys., vol. 10, iss. 39, p. 5963, 2008.

[BibTeX] [Abstract] [PDF] [DOI]

Stochastic simulations of reaction{–}diffusion processes are used extensively for the modeling of complex systems in areas ranging from biology and social sciences to ecosystems and materials processing. These processes often exhibit disparate scales that render their simulation prohibitive even for massive computational resources. The problem is resolved by introducing a novel stochastic multiresolution method that enables the efficient simulation of reaction{–}diffusion processes as modeled by many-particle systems. The proposed method quantifies and efficiently handles the associated stiffness in simulating the system dynamics and its computational efficiency and accuracy are demonstrated in simulations of a model problem described by the Fisher{–}Kolmogorov equation. The method is general and can be applied to other many-particle models of physical processes.

`@article{bayati2008a, author = {Basil Bayati and Philippe Chatelain and Petros Koumoutsakos}, doi = {10.1039/b810795e}, journal = {{Phys. Chem. Chem. Phys.}}, number = {39}, pages = {5963}, publisher = {Royal Society of Chemistry ({RSC})}, title = {Multiresolution stochastic simulations of reaction{\textendash}diffusion processes}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/bayati2008a.pdf}, volume = {10}, year = {2008} }`

- D. Rossinelli, B. Bayati, and P. Koumoutsakos, “Accelerated stochastic and hybrid methods for spatial simulations of reaction–diffusion systems,” Chemical Phys. Lett., vol. 451, iss. 1-3, p. 136–140, 2008.

[BibTeX] [Abstract] [PDF] [DOI]

Spatial distributions characterize the evolution of reaction-diffusion models of several physical, chemical, and biological systems. We present two novel algorithms for the efficient simulation of these models: Spatial tau-Leaping (S tau-Leaping), employing a unified acceleration of the stochastic simulation of reaction and diffusion, and Hybrid tau-Leaping (H tau-Leaping), combining a deterministic diffusion approximation with a tau-Leaping acceleration of the stochastic reactions. The algorithms are validated by solving Fisher’s equation and used to explore the role of the number of particles in pattern formation. The results indicate that the present algorithms have a nearly constant time complexity with respect to the number of events (reaction and diffusion), unlike the exact stochastic simulation algorithm which scales linearly.

`@article{rossinelli2008b, author = {Diego Rossinelli and Basil Bayati and Petros Koumoutsakos}, doi = {10.1016/j.cplett.2007.11.055}, journal = {{Chemical Phys. Lett.}}, month = {jan}, number = {1-3}, pages = {136--140}, publisher = {Elsevier {BV}}, title = {Accelerated stochastic and hybrid methods for spatial simulations of reaction{\textendash}diffusion systems}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/rossinelli2008b.pdf}, volume = {451}, year = {2008} }`

### 2006

- A. Auger, P. Chatelain, and P. Koumoutsakos, “R-leaping: accelerating the stochastic simulation algorithm by reaction leaps,” J. Chem. Phys., vol. 125, iss. 8, p. 84103, 2006.

[BibTeX] [Abstract] [PDF] [DOI]

A novel algorithm is proposed for the acceleration of the exact stochastic simulation algorithm by a predefined number of reaction firings (R-leaping) that may occur across several reaction channels. In the present approach, the numbers of reaction firings are correlated binomial distributions and the sampling procedure is independent of any permutation of the reaction channels. This enables the algorithm to efficiently handle large systems with disparate rates, providing substantial computational savings in certain cases. Several mechanisms for controlling the accuracy and the appearance of negative species are described. The advantages and drawbacks of R-leaping are assessed by simulations on a number of benchmark problems and the results are discussed in comparison with established methods.

`@article{auger2006a, author = {Anne Auger and Philippe Chatelain and Petros Koumoutsakos}, doi = {10.1063/1.2218339}, journal = {{J. Chem. Phys.}}, month = {aug}, number = {8}, pages = {084103}, publisher = {{AIP} Publishing}, title = {R-leaping: Accelerating the stochastic simulation algorithm by reaction leaps}, url = {http://www.cse-lab.ethz.ch/wp-content/papercite-data/pdf/auger2006a.pdf}, volume = {125}, year = {2006} }`