American Institute of Mathematical Sciences

Advanced
2012, 9(3): 487-526. doi: 10.3934/mbe.2012.9.487

A comparison of computational efficiencies of stochastic algorithms in terms of two infection models

H. Thomas Banks 1, , Shuhua Hu 1, , Michele Joyner 2, , Anna Broido 3, , Brandi Canter 2, , Kaitlyn Gayvert 4, and  Kathryn Link 5,

1. 

Center for Research in Scientific Computation, Center for Quantitative Sciences in Biomedicine, North Carolina State University, Raleigh, NC 27695-8212, United States, United States
2. 

Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN 37614-70663, United States, United States
3. 

Department of Mathematics, Boston College, Chestnut Hill, MA 02467-3806, United States
4. 

Department of Mathematics, State University of New York at Geneseo, Geneseo, NY 14454, United States
5. 

Department of Mathematics, Bryn Mawr College, Bryn Mawr, PA 19010-2899, United States

Received  November 2011 Revised  May 2012 Published  July 2012

In this paper, we investigate three particular algorithms: a stochastic simulation algorithm (SSA), and explicit and implicit tau-leaping algorithms. To compare these methods, we used them to analyze two infection models: a Vancomycin-resistant enterococcus (VRE) infection model at the population level, and a Human Immunodeficiency Virus (HIV) within host infection model. While the first has a low species count and few transitions, the second is more complex with a comparable number of species involved. The relative efficiency of each algorithm is determined based on computational time and degree of precision required. The numerical results suggest that all three algorithms have the similar computational efficiency for the simpler VRE model, and the SSA is the best choice due to its simplicity and accuracy. In addition, we have found that with the larger and more complex HIV model, implementation and modification of tau-Leaping methods are preferred.
Keywords: continuous time Markov chain models, Gillespie, tau-leaping, Dynamical models, stochastic simulation algorithms, bacterial and viral infection models..
Mathematics Subject Classification: 60J27, 60J22, 92D2.
Citation: H. Thomas Banks, Shuhua Hu, Michele Joyner, Anna Broido, Brandi Canter, Kaitlyn Gayvert, Kathryn Link. A comparison of computational efficiencies of stochastic algorithms in terms of two infection models. Mathematical Biosciences & Engineering, 2012, 9 (3) : 487-526. doi: 10.3934/mbe.2012.9.487
References:
[1]

B. M. Adams, H. T. Banks, M. Davidian, H. Kwon, H. T. Tran, S. N. Wynne and E. S. Rosenberg, HIV dynamics: Modeling, data analysis, and optimal treatment protocols,, J. Computational and Applied Mathematics, 184 (2005), 10.  doi: 10.1016/j.cam.2005.02.004.  Google Scholar

[2]

B. M. Adams, H. T. Banks, M. Davidian and E. S. Rosenberg, Model fitting and prediction with HIV treatment interruption data, CRSC-TR05-40, NCSU, October, 2005,, Bulletin of Mathematical Biology, 69 (2007), 563.  doi: 10.1007/s11538-006-9140-6.  Google Scholar

[3]

L. J. S. Allen, "An Introduction to Stochastic Processes with Applications to Biology,", Second edition, (2011).   Google Scholar

[4]

P. Bai, H. T. Banks, S. Dediu, A. Y. Govan, M. Last, A. L. Lloyd, H. K. Nguyen, M. S. Olufsen, G. Rempala and B. D. Slenning, Stochastic and deterministic models for agricultural production networks,, Mathematical Biosciences and Engineering, 4 (2007), 373.   Google Scholar

[5]

H. T. Banks, M. Davidian, S. Hu, G. Kepler and E. S. Rosenberg, Modelling HIV immune response and validation with clinical data,, Journal of Biological Dynamics, 2 (2008), 357.   Google Scholar

[6]

D. S. Callaway and A. S. Perelson, HIV-1 infection and low steady state viral loads,, Bulletin of Mathematical Biology, 64 (2001), 29.   Google Scholar

[7]

Y. Cao, D. T. Gillespie and L. R. Petzold, Avoiding negative populations in explicit Poisson tau-leaping,, The Journal of Chemical Physics, 123 (2005).   Google Scholar

[8]

Y. Cao, D. T. Gillespie and L. R. Petzold, Efficient step size selection for the tau-leaping simulation method,, The Journal of Chemical Physics, 124 (2006).   Google Scholar

[9]

Y. Cao, D. T. Gillespie and L. R. Petzold, Adaptive explicit-implicit tau-leaping method with automatic tau selection,, The Journal of Chemical Physics, 126 (2007).   Google Scholar

[10]

N. M. Dixit and A. S. Perelson, Complex patterns of viral load decay under antiretroviral therapy: Influence of pharmacokinetics and intracellular delay,, J. of Theoretical Biology, 226 (2004), 95.   Google Scholar

[11]

D. T. Gillespie, A general method for numerically simulating the stochastic time evolution of coupled chemical reactions,, The Journal of Computational Physics, 22 (1976), 403.  doi: 10.1016/0021-9991(76)90041-3.  Google Scholar

[12]

D. T. Gillespie, Approximate accelerated stochastic simulation of chemically reacting systems,, The Journal of Chemical Physics, 115 (2001), 1716.  doi: 10.1063/1.1378322.  Google Scholar

[13]

D. T. Gillespie and L. R. Petzold, Improved leap-size selection for accelerated stochastic simulation,, The Journal of Chemical Physics, 119 (2003), 8229.  doi: 10.1063/1.1613254.  Google Scholar

[14]

D. T. Gillespie and L. R. Petzold, Stochastic simulation of chemical kinetics,, Annual Review of Physical Chemistry, 58 (2007), 25.   Google Scholar

[15]

G. M. Kepler, H. T. Banks, M. Davidian and E. S. Rosenberg, A model for HCMV infection in immunosuppressed patients,, Mathematical and Computer Modelling, 49 (2009), 1653.  doi: 10.1016/j.mcm.2008.06.003.  Google Scholar

[16]

T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes,, J. Appl. Prob., 7 (1970), 49.   Google Scholar

[17]

T. G. Kurtz, Limit theorems for sequences of pure jump Markov processes approximating ordinary differential processes,, J. Appl. Prob., 8 (1971), 344.   Google Scholar

[18]

H. H. McAdams and A. Arkin, Stochastic mechanisms in gene expression,, PNAS, 94 (1997), 814.  doi: 10.1073/pnas.94.3.814.  Google Scholar

[19]

A. R. Ortiz, H. T. Banks, C. Castillo-Chavez, G. Chowell and X. Wang, A deterministic methodology for estimation of parameters in dynamic Markov chain models,, Journal of Biological Systems, 19 (2011), 71.  doi: 10.1142/S0218339011003798.  Google Scholar

[20]

J. Pahle, Biochemical simulations: Stochastic, approximate stochastic and hybrid approaches,, Brief Bioinform, 10 (2009), 53.  doi: 10.1093/bib/bbn050.  Google Scholar

[21]

A. S. Perelson, P. Essunger, Y. Z. Cao, M. Vesanen, A. Hurley, K. Saksela, M. Markowitz and D. D. Ho, Decaycharacteristics of HIV-1-infected compartments during combination therapy,, Nature, 387 (1997), 187.   Google Scholar

[22]

J. E. Pearson, P. Krapivsky and A. S. Perelson, Stochastic theory of early viral infection: Continuous versus burst production of virions,, PLoS Comput. Biol., 7 (2011).   Google Scholar

[23]

A. S. Perelson and P. W. Nelson, Mathematical analysis of HIV-1 dynamics in vivo,, SIAM Review, 41 (1999), 3.   Google Scholar

[24]

M. Rathinam, L. R. Petzold, Y. Cao and D. T. Gillespie, Stiffness in stochastic chemically reacting systems: The implicit tau-leaping method,, The Journal of Chemical Physics, 119 (2003), 12784.  doi: 10.1063/1.1627296.  Google Scholar

[25]

E. Renshaw, "Modelling Biological Populations in Space and Time,", Cambridge Studies in Mathematical Biology, 11 (1991).   Google Scholar

[26]

D. J. Wilkinson, Stochastic modelling for quantitative description of heterogeneous biological systems,, Nature Reviews Genetics, 10 (2009), 122.  doi: 10.1038/nrg2509.  Google Scholar

show all references

References:
[1]

B. M. Adams, H. T. Banks, M. Davidian, H. Kwon, H. T. Tran, S. N. Wynne and E. S. Rosenberg, HIV dynamics: Modeling, data analysis, and optimal treatment protocols,, J. Computational and Applied Mathematics, 184 (2005), 10.  doi: 10.1016/j.cam.2005.02.004.  Google Scholar

[2]

B. M. Adams, H. T. Banks, M. Davidian and E. S. Rosenberg, Model fitting and prediction with HIV treatment interruption data, CRSC-TR05-40, NCSU, October, 2005,, Bulletin of Mathematical Biology, 69 (2007), 563.  doi: 10.1007/s11538-006-9140-6.  Google Scholar

[3]

L. J. S. Allen, "An Introduction to Stochastic Processes with Applications to Biology,", Second edition, (2011).   Google Scholar

[4]

P. Bai, H. T. Banks, S. Dediu, A. Y. Govan, M. Last, A. L. Lloyd, H. K. Nguyen, M. S. Olufsen, G. Rempala and B. D. Slenning, Stochastic and deterministic models for agricultural production networks,, Mathematical Biosciences and Engineering, 4 (2007), 373.   Google Scholar

[5]

H. T. Banks, M. Davidian, S. Hu, G. Kepler and E. S. Rosenberg, Modelling HIV immune response and validation with clinical data,, Journal of Biological Dynamics, 2 (2008), 357.   Google Scholar

[6]

D. S. Callaway and A. S. Perelson, HIV-1 infection and low steady state viral loads,, Bulletin of Mathematical Biology, 64 (2001), 29.   Google Scholar

[7]

Y. Cao, D. T. Gillespie and L. R. Petzold, Avoiding negative populations in explicit Poisson tau-leaping,, The Journal of Chemical Physics, 123 (2005).   Google Scholar

[8]

Y. Cao, D. T. Gillespie and L. R. Petzold, Efficient step size selection for the tau-leaping simulation method,, The Journal of Chemical Physics, 124 (2006).   Google Scholar

[9]

Y. Cao, D. T. Gillespie and L. R. Petzold, Adaptive explicit-implicit tau-leaping method with automatic tau selection,, The Journal of Chemical Physics, 126 (2007).   Google Scholar

[10]

N. M. Dixit and A. S. Perelson, Complex patterns of viral load decay under antiretroviral therapy: Influence of pharmacokinetics and intracellular delay,, J. of Theoretical Biology, 226 (2004), 95.   Google Scholar

[11]

D. T. Gillespie, A general method for numerically simulating the stochastic time evolution of coupled chemical reactions,, The Journal of Computational Physics, 22 (1976), 403.  doi: 10.1016/0021-9991(76)90041-3.  Google Scholar

[12]

D. T. Gillespie, Approximate accelerated stochastic simulation of chemically reacting systems,, The Journal of Chemical Physics, 115 (2001), 1716.  doi: 10.1063/1.1378322.  Google Scholar

[13]

D. T. Gillespie and L. R. Petzold, Improved leap-size selection for accelerated stochastic simulation,, The Journal of Chemical Physics, 119 (2003), 8229.  doi: 10.1063/1.1613254.  Google Scholar

[14]

D. T. Gillespie and L. R. Petzold, Stochastic simulation of chemical kinetics,, Annual Review of Physical Chemistry, 58 (2007), 25.   Google Scholar

[15]

G. M. Kepler, H. T. Banks, M. Davidian and E. S. Rosenberg, A model for HCMV infection in immunosuppressed patients,, Mathematical and Computer Modelling, 49 (2009), 1653.  doi: 10.1016/j.mcm.2008.06.003.  Google Scholar

[16]

T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes,, J. Appl. Prob., 7 (1970), 49.   Google Scholar

[17]

T. G. Kurtz, Limit theorems for sequences of pure jump Markov processes approximating ordinary differential processes,, J. Appl. Prob., 8 (1971), 344.   Google Scholar

[18]

H. H. McAdams and A. Arkin, Stochastic mechanisms in gene expression,, PNAS, 94 (1997), 814.  doi: 10.1073/pnas.94.3.814.  Google Scholar

[19]

A. R. Ortiz, H. T. Banks, C. Castillo-Chavez, G. Chowell and X. Wang, A deterministic methodology for estimation of parameters in dynamic Markov chain models,, Journal of Biological Systems, 19 (2011), 71.  doi: 10.1142/S0218339011003798.  Google Scholar

[20]

J. Pahle, Biochemical simulations: Stochastic, approximate stochastic and hybrid approaches,, Brief Bioinform, 10 (2009), 53.  doi: 10.1093/bib/bbn050.  Google Scholar

[21]

A. S. Perelson, P. Essunger, Y. Z. Cao, M. Vesanen, A. Hurley, K. Saksela, M. Markowitz and D. D. Ho, Decaycharacteristics of HIV-1-infected compartments during combination therapy,, Nature, 387 (1997), 187.   Google Scholar

[22]

J. E. Pearson, P. Krapivsky and A. S. Perelson, Stochastic theory of early viral infection: Continuous versus burst production of virions,, PLoS Comput. Biol., 7 (2011).   Google Scholar

[23]

A. S. Perelson and P. W. Nelson, Mathematical analysis of HIV-1 dynamics in vivo,, SIAM Review, 41 (1999), 3.   Google Scholar

[24]

M. Rathinam, L. R. Petzold, Y. Cao and D. T. Gillespie, Stiffness in stochastic chemically reacting systems: The implicit tau-leaping method,, The Journal of Chemical Physics, 119 (2003), 12784.  doi: 10.1063/1.1627296.  Google Scholar

[25]

E. Renshaw, "Modelling Biological Populations in Space and Time,", Cambridge Studies in Mathematical Biology, 11 (1991).   Google Scholar

[26]

D. J. Wilkinson, Stochastic modelling for quantitative description of heterogeneous biological systems,, Nature Reviews Genetics, 10 (2009), 122.  doi: 10.1038/nrg2509.  Google Scholar

[1]

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345
[2]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010
[3]

Wei Feng, Michael Freeze, Xin Lu. On competition models under allee effect: Asymptotic behavior and traveling waves. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5609-5626. doi: 10.3934/cpaa.2020256
[4]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168
[5]

Annegret Glitzky, Matthias Liero, Grigor Nika. Dimension reduction of thermistor models for large-area organic light-emitting diodes. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020460
[6]

Yen-Luan Chen, Chin-Chih Chang, Zhe George Zhang, Xiaofeng Chen. Optimal preventive "maintenance-first or -last" policies with generalized imperfect maintenance models. Journal of Industrial & Management Optimization, 2021, 17 (1) : 501-516. doi: 10.3934/jimo.2020149
[7]

Fanni M. Sélley. A self-consistent dynamical system with multiple absolutely continuous invariant measures. Journal of Computational Dynamics, 2021, 8 (1) : 9-32. doi: 10.3934/jcd.2021002
[8]

Sushil Kumar Dey, Bibhas C. Giri. Coordination of a sustainable reverse supply chain with revenue sharing contract. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020165
[9]

Jiahao Qiu, Jianjie Zhao. Maximal factors of order $ d $ of dynamical cubespaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278
[10]

Omid Nikan, Seyedeh Mahboubeh Molavi-Arabshai, Hossein Jafari. Numerical simulation of the nonlinear fractional regularized long-wave model arising in ion acoustic plasma waves. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020466
[11]

Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167
[12]

Yolanda Guerrero–Sánchez, Muhammad Umar, Zulqurnain Sabir, Juan L. G. Guirao, Muhammad Asif Zahoor Raja. Solving a class of biological HIV infection model of latently infected cells using heuristic approach. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020431
[13]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441
[14]

Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323
[15]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375
[16]

Mingjun Zhou, Jingxue Yin. Continuous subsonic-sonic flows in a two-dimensional semi-infinitely long nozzle. Electronic Research Archive, , () : -. doi: 10.3934/era.2020122
[17]

Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323
[18]

Emre Esentürk, Juan Velazquez. Large time behavior of exchange-driven growth. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 747-775. doi: 10.3934/dcds.2020299
[19]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264
[20]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

2018 Impact Factor: 1.313

Tools

Metrics

  • PDF downloads (71)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences