×

Multilevel hybrid split-step implicit tau-leap. (English) Zbl 1357.65005

Summary: In biochemically reactive systems with small copy numbers of one or more reactant molecules, the dynamics is dominated by stochastic effects. To approximate those systems, discrete state-space and stochastic simulation approaches have been shown to be more relevant than continuous state-space and deterministic ones. In systems characterized by having simultaneously fast and slow timescales, existing discrete space-state stochastic path simulation methods, such as the stochastic simulation algorithm (SSA) and the explicit tau-leap (explicit-TL) method, can be very slow. Implicit approximations have been developed to improve numerical stability and provide efficient simulation algorithms for those systems. Here, we propose an efficient Multilevel Monte Carlo (MLMC) method in the spirit of the work by D. F. Anderson and D. J. Higham [Multiscale Model. Simul. 10, No. 1, 146–179 (2012; Zbl 1262.60072)]. This method uses split-step implicit tau-leap (SSI-TL) at levels where the explicit-TL method is not applicable due to numerical stability issues. We present numerical examples that illustrate the performance of the proposed method.

MSC:

65C05 Monte Carlo methods
60J75 Jump processes (MSC2010)
60J27 Continuous-time Markov processes on discrete state spaces
65G20 Algorithms with automatic result verification
92C40 Biochemistry, molecular biology
60K35 Interacting random processes; statistical mechanics type models; percolation theory
92C45 Kinetics in biochemical problems (pharmacokinetics, enzyme kinetics, etc.)

Citations:

Zbl 1262.60072

Software:

bootstrap; S-ROCK
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abdulle, A., Cirilli, S.: Stabilized methods for stiff stochastic systems. Compt. R. Math. 345(10), 593-598 (2007) · Zbl 1128.65004
[2] Abdulle, A., Cirilli, S.: S-rock: Chebyshev methods for stiff stochastic differential equations. SIAM J. Sci. Comput. 30(2), 997-1014 (2008) · Zbl 1159.60329 · doi:10.1137/070679375
[3] Abdulle, A., Hu, Y., Li, T.: Chebyshev methods with discrete noise: the tau-rock methods. J. Comput. Math. 28(2), 195-217 (2010) · Zbl 1224.65009
[4] Abdulle, A., Li, T.: S-rock methods for stiff Ito sdes. Commun. Math Sci. 6(4), 845-868, 12 (2008) · Zbl 1162.60330 · doi:10.4310/CMS.2008.v6.n4.a3
[5] Ahn, T., Sandu, A., Han, X.: Implicit simulation methods for stochastic chemical kinetics. CoRR, arXiv:1303.3614 (2013) · Zbl 07246332
[6] Anderson, D., Higham, D.: Multilevel Monte Carlo for continuous Markov chains, with applications in biochemical kinetics. SIAM Multiscal Model. Simul. 10 (1) (2012) · Zbl 1262.60072
[7] Anderson, D.F.: A modified next reaction method for simulating chemical systems with time dependent propensities and delays. J. Chem. Phys. 127(21), 214107 (2007) · doi:10.1063/1.2799998
[8] Anderson, D.F.: Incorporating postleap checks in tau-leaping. J. Chem. Phys. 128(5), 054103 (2008) · doi:10.1063/1.2819665
[9] Anderson, D.F., Ganguly, A., Kurtz, T.G.: Error analysis of tau-leap simulation methods. The Annals of Applied Probability, 2226-2262 (2011) · Zbl 1234.60066
[10] Anderson, D.F., Higham, D.J., Sun, Y.: Complexity of multilevel Monte Carlo tau-leaping. SIAM J. Numer. Anal. 52(6), 3106-3127 (2014) · Zbl 1327.60136 · doi:10.1137/130940761
[11] Anderson, D.F., Kurtz, T.G.: Stochastic analysis of biochemical systems. Springer (2015) · Zbl 1402.92004
[12] Brauer, F., Castillo-Chavez, C.: Mathematical models in population biology and epidemiology (texts in applied mathematics), 2nd edn. Springer (2011) · Zbl 1302.92001
[13] Cinlar, E.: Probability and stochastics, volume 261 of Graduate texts in Mathematics. Springer (2011) · Zbl 1226.60001
[14] Cao, Y., Gillespie, D.T., Petzold, L.R.: Avoiding negative populations in explicit Poisson tau-leaping. J. Chem. Phys. 123(5), 054104+ (2005) · doi:10.1063/1.1992473
[15] Cao, Y., Gillespie, D.T., Petzold, L.R.: Efficient step size selection for the tau-leaping simulation method. J. Chem. Phys. 124(4), 044109 (2006) · doi:10.1063/1.2159468
[16] Cao, Y., Petzold, L.: Trapezoidal tau-leaping formula for the stochastic simulation of biochemical systems. In: Foundations of Systems Biology in Engineering (FOSBE), pp 149-152 (2005)
[17] Cao, Y., Petzold, L., Rathinam, M., Gillespie, D.: The numerical stability of leaping methods for stochastic simulation of chemically reacting systems. J. Chem Phys. 121(24), 12169-12178, 22 (2004) · doi:10.1063/1.1823412
[18] Collier, N., Haji-Ali, A.-L., Nobile, F., von Schwerin, E., Tempone, R.: A continuation multilevel Monte Carlo algorithm. BIT Numer. Math. 55(2), 399-432 (2014) · Zbl 1317.65030 · doi:10.1007/s10543-014-0511-3
[19] Duffie, D., Glynn, P.: Efficient Monte Carlo simulation of security prices. Annals of Applied Probability, 897-905 (1995) · Zbl 0877.65099
[20] Efron, B., Tibshirani, R.J.: An Introduction to the Bootstrap. Chapman & Hall, New York (1993) · Zbl 0835.62038 · doi:10.1007/978-1-4899-4541-9
[21] Engblom, S.: On the stability of stochastic jump kinetics. Appl. Math. 5, 3217-3239 (2014) · Zbl 1042.54003 · doi:10.4236/am.2014.519300
[22] Ethier, S.N., Kurtz, T.G.: Markov Processes: characterization and convergence (Wiley Series in Probability and Statistics), 2nd edn., vol. 9. Wiley-Interscience (2005) · Zbl 1173.92010
[23] Giles, M.: Multi-level Monte Carlo path simulation. Oper. Res. 53(3), 607-617 (2008) · Zbl 1167.65316 · doi:10.1287/opre.1070.0496
[24] Gillespie, D.T.: A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. J. Comput. Phys. 22, 403-434 (1976) · doi:10.1016/0021-9991(76)90041-3
[25] Gillespie, D.T.: Approximate accelerated stochastic simulation of chemically reacting systems. J. Chem. Phys. 115, 1716-1733 (2001) · doi:10.1063/1.1378322
[26] Gupta, A., Briat, C., Khammash, M.: A scalable computational framework for establishing long-term behavior of stochastic reaction networks, vol. 10 (2014) · Zbl 1317.65030
[27] Hensel, S., Rawlings, J., Yin, J.: Stochastic kinetic modeling of vesicular stomatitis virus intracellular growth. Bull. Math. Biol. 71(7), 1671-1692 (2009) · Zbl 1173.92010 · doi:10.1007/s11538-009-9419-5
[28] Higham, D.J., Mao, X., Stuart, A.M.: Strong convergence of Euler-type methods for nonlinear stochastic differential equations. SIAM J. Numer. Anal. 40(3), 1041-1063 (2002) · Zbl 1026.65003 · doi:10.1137/S0036142901389530
[29] Hu, Y., Li, T., Min, B.: The weak convergence analysis of tau-leaping methods: revisited. Communication Mathematics Science (2011) · Zbl 1281.65011
[30] Aparicio, H.S.J.: Population dynamics: Poisson approximation and its relation to the Langevin process. Physical Review Letters, 4183 (2001)
[31] Kloeden, P.E., Platen, E.: Numerical Solution of Stochastic Differential Equations. Springer, New York (2011). corrected edition · Zbl 0752.60043
[32] Lester, C., Yates, C.A., Giles, M.B., Baker, R.E.: An adaptive multi-level simulation algorithm for stochastic biological systems. J. Chem. Phys. 142(2), 024113 (2015) · doi:10.1063/1.4904980
[33] Li, T.: Analysis of explicit tau-leaping schemes for simulating chemically reacting systems. Multiscale Model. Simul. 6(2), 417-436 (2007) · Zbl 1145.92041 · doi:10.1137/06066792X
[34] Moraes, A., Tempone, R., Vilanova, P.: Hybrid Chernoff tau-leap. Multiscale Model. Simul. 12(2), 581-615 (2014) · Zbl 1338.65013 · doi:10.1137/130925657
[35] Moraes, A., Tempone, R., Vilanova, P.: Multilevel adaptive reaction-splitting simulation method for stochastic reaction networks. preprint arXiv:1406.1989 (2015) · Zbl 1355.65020
[36] Moraes, A., Tempone, R., Vilanova, P.: Multilevel hybrid Chernoff tau-leap. BIT Annals of Numerical Mathematics, 1-51 (2015) · Zbl 1348.60112
[37] Rathinam, M.: Moment growth bounds on continuous time Markov processes on non-negative integer lattices. Q. Appl. Math. 73, 347-364 (2015) · Zbl 1317.60092 · doi:10.1090/S0033-569X-2015-01372-7
[38] Rathinam, M.: Convergence of moments of tau leaping schemes for unbounded Markov processes on integer lattices. SIAM J. Numer. Anal. 54(1), 415-439 (2016) · Zbl 1346.60126 · doi:10.1137/15M1010166
[39] Rathinam, M., El-Samad, H.: Reversible-equivalent-monomolecular tau: a leaping method for “small number and stiff” stochastic chemical systems. J. Comput. Phys. 224(2), 897-923 (2007) · Zbl 1118.80008 · doi:10.1016/j.jcp.2006.10.034
[40] Rathinam, M., Petzold, L., Cao, Y., Gillespie, D.T.: Stiffness in stochastic chemically reacting systems: the implicit tau-leaping method. J. Chem. Phys. 119 (24), 12784-12794 (2003) · doi:10.1063/1.1627296
[41] Rathinam, M., Petzold, L.R., Cao, Y., Gillespie, D.T.: Consistency and stability of tau-leaping schemes for chemical reaction systems. Multiscale Model. Simul. 4(3), 867-895 (2005). (electronic) · Zbl 1089.60516 · doi:10.1137/040603206
[42] Srivastava, R., You, L., Summers, J., Yin, J.: Stochastic vs. deterministic modeling of intracellular viral kinetics. J. Theor. Biol. 218(3), 309-321 (2002) · doi:10.1006/jtbi.2002.3078
[43] Tian, T., Burrage, K.: Binomial leap methods for simulating stochastic chemical kinetics. J. Chem Phys. 121(21), 10356-10364 (2004) · doi:10.1063/1.1810475
[44] Yang, Y., Rathinam, M., Shen, J.: Integral tau methods for stiff stochastic chemical systems. J. Chem. Phys. 134(4) (2011) · Zbl 1317.65030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.