Efficient simulation of stochastic chemical kinetics with the Stochastic Bulirsch-Stoer extrapolation method

BMC Systems Biology

Manuel Barrio¹  Konstantinos C Zygalakis⁴  Kevin Burrage²  Tamás Székely³ 

[1] Departamento de Informática, Universidad de Valladolid, 47011 Valladolid, Spain;Department of Mathematics, Queensland University of Technology, Brisbane, Qld 4001, Australia;Department of Computer Science, University of Oxford, Oxford, OX1 3QD, UK;Mathematical Sciences, University of Southampton, Southampton, SO17 1BJ, UK

关键词: High-order methods;    τ-leap;    Bulirsch-Stoer;    Discrete stochastic methods;    Stochastic simulation;   

Others  :  864942
DOI  :  10.1186/1752-0509-8-71

 received in 2013-01-22, accepted in 2014-06-05,  发布年份 2014

【 摘 要 】

Background

Biochemical systems with relatively low numbers of components must be simulated stochastically in order to capture their inherent noise. Although there has recently been considerable work on discrete stochastic solvers, there is still a need for numerical methods that are both fast and accurate. The Bulirsch-Stoer method is an established method for solving ordinary differential equations that possesses both of these qualities.

Results

In this paper, we present the Stochastic Bulirsch-Stoer method, a new numerical method for simulating discrete chemical reaction systems, inspired by its deterministic counterpart. It is able to achieve an excellent efficiency due to the fact that it is based on an approach with high deterministic order, allowing for larger stepsizes and leading to fast simulations. We compare it to the Euler τ-leap, as well as two more recent τ-leap methods, on a number of example problems, and find that as well as being very accurate, our method is the most robust, in terms of efficiency, of all the methods considered in this paper. The problems it is most suited for are those with increased populations that would be too slow to simulate using Gillespie’s stochastic simulation algorithm. For such problems, it is likely to achieve higher weak order in the moments.

Conclusions

The Stochastic Bulirsch-Stoer method is a novel stochastic solver that can be used for fast and accurate simulations. Crucially, compared to other similar methods, it better retains its high accuracy when the timesteps are increased. Thus the Stochastic Bulirsch-Stoer method is both computationally efficient and robust. These are key properties for any stochastic numerical method, as they must typically run many thousands of simulations.

【 授权许可】

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

【 图 表 】

【 参考文献 】

• [1]Arkin A, Ross J, McAdams HH: Stochastic kinetic analysis of developmental pathway bifurcation in phage λ-infected Escherichia coli cells. Genetics 1998, 149:1633-1648.
• [2]Kaern M, Elston T, Blake W, Collins J: Stochasticity in gene expression: from theories to phenotypes. Nat Rev Genet 2005, 6:451-464.
• [3]Munsky B, Neuert G, van Oudenaarden A: Using gene expression noise to understand gene regulation. Science 2012, 336:183.
• [4]Fedoroff N, Fontana W: Small numbers of big molecules. Science 2002, 297:1129-1131.
• [5]Elowitz M, Levine A, Siggia E, Swain P: Stochastic gene expression in a single cell. Science 2002, 297:1183-1186.
• [6]Gillespie DT, Mangel M: Conditioned averages in chemical kinetics. J Chem Phys 1981, 75:704-709.
• [7]Goutsias J: Classical versus stochastic kinetics modeling of biochemical reaction systems. Biophys J 2007, 92:2350-2365.
• [8]Wilkinson DJ: Stochastic modelling for quantitative description of heterogeneous biological systems. Nat Rev Genet 2009, 10:122-133.
• [9]Kurtz TG: Limit theorems for sequences of jump Markov processes approximating ordinary differential processes. J Appl Probab 1971, 8:344-356.
• [10]Gillespie DT: Exact stochastic simulation of coupled chemical reactions. J Phys Chem 1977, 81:2340-2361.
• [11]Gillespie DT: Stochastic simulation of chemical kinetics. Annu Rev Phys Chem 2007, 58:35-55.
• [12]Gillespie DT: Approximate accelerated stochastic simulation of chemically reacting systems. J Chem Phys 2001, 115:1716-1733.
• [13]Gillespie DT, Petzold LR: Improved leap-size selection for accelerated stochastic simulation. J Chem Phys 2003, 119:8229-8234.
• [14]Cao Y, Gillespie DT, Petzold LR: Efficient step size selection for the tau-leaping simulation method. J Chem Phys 2006, 124:044109.
• [15]Tian TH, Burrage K: Binomial leap methods for simulating stochastic chemical kinetics. J Chem Phys 2004, 121:10356-10364.
• [16]Chatterjee A, Vlachos DG, Katsoulakis MA: Binomial distribution based tau-leap accelerated stochastic simulation. J Chem Phys 2005, 122:024112.
• [17]Peng X, Zhou W, Wang Y: Efficient binomial leap method for simulating chemical kinetics. J Chem Phys 2007, 126:224109.
• [18]Pettigrew MF, Resat H: Multinomial tau-leaping method for stochastic kinetic simulations. J Chem Phys 2007, 126:084101.
• [19]Xu Z, Cai X: Unbiased tau-leap methods for stochastic simulation of chemically reacting systems. J Chem Phys 2008, 128:154112.
• [20]Hu Y, Li T: Highly accurate tau-leaping methods with random corrections. J Chem Phys 2009, 130:124109.
• [21]Hu Y, Li T, Min B: A weak second order tau-leaping method for chemical kinetic systems. J Chem Phys 2011, 135:024113.
• [22]Székely T Jr., Burrage K, Erban R, Zygalakis KC: A higher-order numerical framework for stochastic simulation of chemical reaction systems. BMC Syst Biol 2012, 6:85.
• [23]Richardson LF: The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam. Phil Trans Roy Soc Lond 1910, 210:307-357.
• [24]Hairer E, Nørsett SP, Wanner G: Solving Ordinary Differential Equations: Nonstiff Problems. 2nd edition. Berlin: Springer-Verlag; 1993.
• [25]Bulirsch R, Stoer J: Numerical treatment of ordinary differential equations by extrapolation methods. Numerische Mathematik 1966, 8:1-13.
• [26]Deuflhard P: Recent progress in extrapolation methods for ordinary differential equations. SIAM Rev 1985, 27(4):505-535.
• [27]Gragg WB: On extrapolation algorithms for ordinary initial value problems. SIAM J Numer Anal 1965, 2:384-403.
• [28]Press WH, Teukolsky SA, Vetterling WT, Flannery BP: Numerical Recipes in C: The Art of Scientific Computing. 2nd edition. Cambridge: Cambridge University Press; 1992.
• [29]Kurtz TG: Strong approximation theorems for density dependent Markov chains. Stochastic Processes Appl 1978, 6:223-240.
• [30]van Kampen NG: Stochastic Processes in Physics and Chemistry. 3rd edition. Amsterdam: Elsevier; 2007.
• [31]Goutsias J, Jenkinson G: Markovian dynamics on complex reaction networks. Phys Rep 2013, 529:199-264.
• [32]Kurtz TG: Representations of Markov processes as multiparameter time changes. Ann Probab 1980, 8:682-715.
• [33]Marquez-Lago T, Burrage K: Binomial tau-leap spatial stochastic simulation algorithm for applications in chemical kinetics. J Chem Phys 2007, 127:104101.
• [34]Elf J, Ehrenberg M: Spontaneous separation of bi-stable biochemical systems into spatial domains of opposite phases. Syst Biol 2004, 1:230-236.
• [35]Rathinam M, Petzold LR, Cao Y, Gillespie DT: Consistency and stability of tau-leaping schemes for chemical reaction systems. Multiscale Model Simul 2005, 4(3):867-895.
• [36]Li T: Analysis of explicit tau-leaping schemes for simulating chemically reacting systems. Multiscale Model Simul 2007, 6(2):417-436.
• [37]Burrage K, Tian T: Poisson Runge-Kutta methods for chemical reaction systems. In Advances in Scientific Computing and Applications. Edited by Sun YLW, Tang T. Beijing/New York: Science Press; 2004:82-96.
• [38]Anderson DF, Ganguly A, Kurtz TG: Error analysis of tau-leap simulation methods. Ann Appl Probab 2011, 21(6):2226-2262.
• [39]Hu Y, Li T, Min B: The weak convergence analysis of tau-leaping methods: revisited. Comm Math Sci 2011, 9:965-996.
• [40]Burrage K, Burrage PM: Order conditions of stochastic Runge–Kutta methods by B-Series. SIAM J Numer Anal 2000, 38(5):1626-1646.
• [41]Milstein GN, Tretyakov MV: Numerical methods in the weak sense for stochastic differential equations with small noise. SIAM J Numer Anal 1997, 34:2142-2167.
• [42]Milstein GN, Tretyakov MV: Mean-square numerical methods for stochastic differential equations with small noises. SIAM J Sci Comput 1997, 18:1067-1087.
• [43]Buckwar E, Rößler A, Winkler R: Stochastic Runge-Kutta methods for Ito SODEs with small noise. SIAM J Sci Comput 2010, 32:1789-1808.
• [44]Rué P, Villa-Freixà J, Burrage K: Simulation methods with extended stability for stiff biochemical kinetics. BMC Syst Biol 2010, 4:110-123.
• [45]Cao Y, Gillespie DT, Petzold LR: The adaptive explicit-implicit tau-leaping method with automatic tau selection. J Chem Phys 2007, 126:224101.
• [46]Goutsias J: Quasiequilibrium approximation of fast reaction kinetics in stochastic biochemical systems. J Chem Phys 2005, 122:184102.
• [47]MacNamara S, Burrage K, Sidje R: Multiscale modeling of chemical kinetics via the master equation. Multiscale Model Simul 2008, 6(4):1146-1168.