Efficient stochastic simulation

A large part of my research focusses on developing efficient algorithms for simulating stochastic reaction-diffusion models.

Multi-level Monte Carlo methods

Discrete-state, continuous-time Markov models are widely used in the modelling of biochemical reaction networks. Their complexity often precludes analytic solution, and so we rely on Monte Carlo simulation to estimate system statistics of interest. Perhaps the most widely used method is the Gillespie algorithm; it is exact but computationally complex. As such, approximate stochastic simulation algorithms such as the tau-leap algorithm are often used. Sample paths are simulated by taking leaps of length tau through time and using an approximate method to generate reactions within leaps. Tau must be held relatively small to avoid significant bias, but this often entails computational times similar to the Gillespie algorithm.

The multi-level method of Anderson and Higham tackles this problem by cleverly generating a suite of paths with different accuracy to estimate statistics. A base estimator is computed using many (cheap) paths at low accuracy. The bias inherent in this estimator is then reduced using a number of correction estimators. Each correction term is estimated using a collection of (expensive) paired paths; one path of each pair is generated at a higher accuracy compared to the other. By sharing randomness between these paired paths only a relatively small number of pairs are required to calculate each correction term.

In the original multi-level method, paths are simulated using the tau-leap technique with a fixed value of tau. This approach can result in poor performance where the reaction activity of a system changes substantially over the course of a sample path. We have developed a method that allows for adaptive tau-leaping within the multi-level framework.

  • C. Lester, M. B. Giles, C. A. Yates and R. E. Baker (2015). An adaptive multi-level simulation algorithm for stochastic biological systems. J. Chem. Phys. 124:024113. DOI
  • C. Lester, R. E. Baker, M. B. Giles and C. A. Yates (2015). A guide to efficient discrete-state multi-level simulation of stochastic biological systems. arXiv
  • D. Wilson and R. E. Baker (2016). Multi-level methods and approximating distribution functions. arXiv

Efficient simulation of reaction-diffusion systems

My group also explores other means by which one can efficiently simulate paths for lattice-based reaction-diffusion systems. A recent example of our work is the extension of random walk algorithms to include jumps to non-nearest neighbour sites, and we are currently exploring different methods for coarse graining volume exclusion models, and connecting models at different scales.

  • P. R. Taylor, R. E. Baker and C. A. Yates (2015). Deriving appropriate boundary conditions, and accelerating position-jump simulations, of diffusion using non-local jumping. Phys. Biol. 12(1):016006. DOI
  • P. R. Taylor, C. A. Yates, M. J. Simpson and R. E. Baker (2015). Reconciling transport models across scales: the role of volume exclusion. Phys. Rev. E Rapid Communication 92:040701(R). DOI
  • P. R. Taylor, R. E. Baker, M. J. Simpson and C. A. Yates (2016). Coupling volume-excluding compartment-based models of diffusion at different scales: Voronoi and pseudo-compartment approaches. arXiv