A higher-order numerical framework for stochastic simulation of chemical reaction systems

BMC Systems Biology

Konstantinos C Zygalakis³  Radek Erban¹  Kevin Burrage²  Tamás Székely⁴ 

[1] Mathematical Institute, University of Oxford, Oxford, OX1 3LB, UK;Department of Mathematics, Queensland University of Technology, Brisbane, Qld 4001, Australia;Mathematics Section, École Polytechnique Fédérale de Lausanne, Station 8, CH-1015 Lausanne, Switzerland;Department of Computer Science, University of Oxford, Oxford, OX1 3QD, UK

关键词: Monte Carlo error;    High-order methods;    τ-leap;    Stochastic simulation algorithms;   

Others  :  1143851
DOI  :  10.1186/1752-0509-6-85

 received in 2012-02-28, accepted in 2012-06-22,  发布年份 2012

【 摘 要 】

Background

In this paper, we present a framework for improving the accuracy of fixed-step methods for Monte Carlo simulation of discrete stochastic chemical kinetics. Stochasticity is ubiquitous in many areas of cell biology, for example in gene regulation, biochemical cascades and cell-cell interaction. However most discrete stochastic simulation techniques are slow. We apply Richardson extrapolation to the moments of three fixed-step methods, the Euler, midpoint and θ-trapezoidal τ-leap methods, to demonstrate the power of stochastic extrapolation. The extrapolation framework can increase the order of convergence of any fixed-step discrete stochastic solver and is very easy to implement; the only condition for its use is knowledge of the appropriate terms of the global error expansion of the solver in terms of its stepsize. In practical terms, a higher-order method with a larger stepsize can achieve the same level of accuracy as a lower-order method with a smaller one, potentially reducing the computational time of the system.

Results

By obtaining a global error expansion for a general weak first-order method, we prove that extrapolation can increase the weak order of convergence for the moments of the Euler and the midpoint τ-leap methods, from one to two. This is supported by numerical simulations of several chemical systems of biological importance using the Euler, midpoint and θ-trapezoidal τ-leap methods. In almost all cases, extrapolation results in an improvement of accuracy. As in the case of ordinary and stochastic differential equations, extrapolation can be repeated to obtain even higher-order approximations.

Conclusions

Extrapolation is a general framework for increasing the order of accuracy of any fixed-step stochastic solver. This enables the simulation of complicated systems in less time, allowing for more realistic biochemical problems to be solved.

【 授权许可】

   
2012 Székely et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

Figure 11.

Figure 12.

【 参考文献 】

• [1]McAdams HH, Arkin A: It’s a noisy business! Genetic regulation at the nanomolar scale. Trends Genet 1999, 15:65-69.
• [2]Elowitz M, Levine A, Siggia E, Swain P: Stochastic gene expression in a single cell. Science 2002, 297:1183-1186.
• [3]Fedoroff N, Fontana W: Small numbers of big molecules. Science 2002, 297:1129-1131.
• [4]Kaern M, Elston T, Blake W, Collins J: Stochasticity in gene expression: from theories to phenotypes. Nature Rev Genet 2005, 6:451-464.
• [5]Wilkinson DJ: Stochastic modelling for quantitative description of heterogeneous biological systems. Nature Rev Genet 2009, 10:122-133.
• [6]Erban R, Chapman SJ, Kevrekidis I, Vejchodsky T: Analysis of a stochastic chemical system close to a SNIPER bifurcation of its mean-field model. SIAM J Appl Mathematics 2009, 70:984-1016.
• [7]McQuarrie DA: Stochastic approach to chemical kinetics. J Appl Probability 1967, 4:413-478.
• [8]Gillespie DT: A rigorous derivation of the Chemical Master Equation. Physica A 1992, 188:404-425.
• [9]Gillespie DT: Exact stochastic simulation of coupled chemical reactions. J Phys Chem 1977, 81:2340-2361.
• [10]Gillespie DT: Approximate accelerated stochastic simulation of chemically reacting systems. J Chem Phys 2001, 115:1716-1733.
• [11]Gillespie DT, Petzold LR: Improved leap-size selection for accelerated stochastic simulation. J Chem Phys 2003, 119:8229-8234.
• [12]Cao Y, Gillespie DT, Petzold LR: Efficient step size selection for the tau-leaping simulation method. J Chem Phys 2006, 124:044109.
• [13]Rathinam M, Petzold LR, Cao Y, Gillespie DT: Consistency and stability of tau-leaping schemes for chemical reaction systems. Multiscale Model Simul 2005, 4:867-895.
• [14]Li T: Analysis of explicit tau-Leaping schemes for simulating chemically reacting systems. Multiscale Model Simul 2007, 6:417-436.
• [15]Anderson DF, Ganguly A, Kurtz TG: Error analysis of tau-leap simulation methods. Ann Appl Probability 2011, 21:2226-2262.
• [16]Hu Y, Li T, Min B: The weak convergence analysis of tau-leaping methods: revisited. Commun Math Sciin press
• [17]Tian TH, Burrage K: Binomial leap methods for simulating stochastic chemical kinetics. J Chem Phys 2004, 121:10356-10364.
• [18]Hu Y, Li T: Highly accurate tau-leaping methods with random corrections. J Chem Phys 2009, 130:124109.
• [19]Anderson DF, Koyama M: Weak error analysis of numerical methods for stochastic models of population processes. 2011. Arxiv.org:1102.2922
• [20]Hu Y, Li T, Min B: A weak second order tau-leaping method for chemical kinetic systems. J Chem Phys 2011, 135:024113.
• [21]Anderson DF, Mattingly JC: A weak trapezoidal method for a class of stochastic differential equations. Commun Math Sci 2011, 9:301-318.
• [22]Hairer E, Nørsett SP, Wanner G: Solving ordinary differential equations: Nonstiff problems. Berlin: Springer; 1993.
• [23]Talay D, Tubaro L: Expansion of the global error for numerical schemes solving stochastic differential equations. Stochastic Anal Appl 1990, 8:483-509.
• [24]Rué P, Villa-Freixà J, Burrage K: Simulation methods with extended stability for stiff biochemical kinetics. BMC Sys Biol 2010, 4:110-123. BioMed Central Full Text
• [25]Gibson M, Bruck J: Efficient exact stochastic simulation of chemical systems with many species and many channels. J Phys Chem A 2000, 104:1876-1889.
• [26]Cao Y, Li H, Petzold LR: Efficient formulation of the stochastic simulation algorithm for chemically reacting systems. J Chem Phys 2004, 121:4059-4067.
• [27]Chatterjee A, Vlachos DG, Katsoulakis MA: Binomial distribution based tau-leap accelerated stochastic simulation. J Chem Phys 2005, 122:024112.
• [28]Cao Y, Gillespie DT, Petzold LR: Avoiding negative populations in explicit Poisson tau-leaping. J Chem Phys 2005, 123:054104.
• [29]Yates CA, Burrage K: Look before you leap: A confidence-based method for selecting species criticality while avoiding negative populations in tau-leaping. J Chem Phys 2011, 134:084109.
• [30]Liu XQ, Li CW: Weak approximation and extrapolations of stochastic differential equations with jumps. SIAM J Numer Anal 2000, 37:1747-1767.
• [31]Shohat J, Tamarkin JD: The Problem of Moments. New York: American Mathematical Society; 1943.
• [32]Jahnke T, Huisinga W: Solving the Chemical Master Equation for monomolecular reaction systems analytically. J Math Biol 2007, 54:1-26.
• [33]Gadgil C, Lee C, Othmer H: A stochastic analysis of first-order reaction networks. Bull Math Biol 2005, 67:901-946.
• [34]van Kampen NG: Stochastic Processes in Physics and Chemistry. Amsterdam: Elsevier; 2007.
• [35]Shahrezaei V, Swain PS: Analytical distributions for stochastic gene expression. Proc Nat Acad Sci USA 2008, 105:17256-17261.
• [36]Marquez-Lago T, Stelling J: Counter-intuitive stochastic behavior of simple gene circuits with negative feedbacks. Biophys J 2010, 98:1742-1750.
• [37]Marquez-Lago T, Burrage K: Binomial tau-leap spatial stochastic simulation algorithm for applications in chemical kinetics. J Chem Phys 2007, 127:104101.
• [38]Schlögl F: Chemical reaction models for nonequilibrium phase-transitions. Z Phys 1972, 253:147-161.
• [39]MacNamara S, Burrage K, Sidje RB: Multiscale modeling of chemical kinetics via the master equation. Multiscale Model Simul 2007, 6:1146-1168.
• [40]Mélykúti B, Burrage K, Zygalakis KC: Fast stochastic simulation of biochemical reaction systems by alternative formulations of the chemical Langevin equation. J Chem Phys 2010, 132:164109.
• [41]Liu JS: Monte Carlo strategies in scientific computing. New York: Springer; 2001.
• [42]Anderson DF, Higham DJ: Multi-level Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics. SIAM Multiscale Model Simul 2012, 10:146-179.
• [43]Kebaier A: Statistical Romberg extrapolation: A new variance reduction method and applications to option pricing. Ann Appl Probability 2005, 15:2681-2705.
• [44]Giles MB: Multilevel Monte Carlo path simulation. Operations Res 2008, 56:607-617.
• [45]Rößler A: Stochastic Taylor expansions for the expectation of functionals of diffusion processes. Stochastic Anal App 2004, 22:1553-1576.