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-49. 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-584. 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, CRC Press, Boca Raton, FL, 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-402.  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-385.  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-64. 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), 054104. 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), 044109. 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), 224101. 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-109.  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-434. 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-1733. 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-8234. 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-55. 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-1663. 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-58.  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-356.  Google Scholar

[18]

H. H. McAdams and A. Arkin, Stochastic mechanisms in gene expression, PNAS, 94 (1997), 814-819. 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-100. doi: 10.1142/S0218339011003798.  Google Scholar

[20]

J. Pahle, Biochemical simulations: Stochastic, approximate stochastic and hybrid approaches, Brief Bioinform, 10 (2009), 53-64. 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-191. 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), e1001058, 17 pp.  Google Scholar

[23]

A. S. Perelson and P. W. Nelson, Mathematical analysis of HIV-1 dynamics in vivo, SIAM Review, 41 (1999), 3-44.  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-12794. doi: 10.1063/1.1627296.  Google Scholar

[25]

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

[26]

D. J. Wilkinson, Stochastic modelling for quantitative description of heterogeneous biological systems, Nature Reviews Genetics, 10 (2009), 122-133. 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-49. 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-584. 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, CRC Press, Boca Raton, FL, 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-402.  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-385.  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-64. 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), 054104. 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), 044109. 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), 224101. 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-109.  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-434. 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-1733. 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-8234. 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-55. 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-1663. 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-58.  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-356.  Google Scholar

[18]

H. H. McAdams and A. Arkin, Stochastic mechanisms in gene expression, PNAS, 94 (1997), 814-819. 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-100. doi: 10.1142/S0218339011003798.  Google Scholar

[20]

J. Pahle, Biochemical simulations: Stochastic, approximate stochastic and hybrid approaches, Brief Bioinform, 10 (2009), 53-64. 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-191. 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), e1001058, 17 pp.  Google Scholar

[23]

A. S. Perelson and P. W. Nelson, Mathematical analysis of HIV-1 dynamics in vivo, SIAM Review, 41 (1999), 3-44.  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-12794. doi: 10.1063/1.1627296.  Google Scholar

[25]

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

[26]

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

[1]

Sukhitha W. Vidurupola, Linda J. S. Allen. Basic stochastic models for viral infection within a host. Mathematical Biosciences & Engineering, 2012, 9 (4) : 915-935. doi: 10.3934/mbe.2012.9.915
[2]

Zhengyan Wang, Guanghua Xu, Peibiao Zhao, Zudi Lu. The optimal cash holding models for stochastic cash management of continuous time. Journal of Industrial & Management Optimization, 2018, 14 (1) : 1-17. doi: 10.3934/jimo.2017034
[3]

Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1
[4]

Samuel N. Cohen. Uncertainty and filtering of hidden Markov models in discrete time. Probability, Uncertainty and Quantitative Risk, 2020, 5 (0) : 4-. doi: 10.1186/s41546-020-00046-x
[5]

Yuri Nechepurenko, Michael Khristichenko, Dmitry Grebennikov, Gennady Bocharov. Bistability analysis of virus infection models with time delays. Discrete & Continuous Dynamical Systems - S, 2020, 13 (9) : 2385-2401. doi: 10.3934/dcdss.2020166
[6]

Heikki Haario, Leonid Kalachev, Marko Laine. Reduction and identification of dynamic models. Simple example: Generic receptor model. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 417-435. doi: 10.3934/dcdsb.2013.18.417
[7]

Lifeng Chen, Jifa Jiang. Stochastic epidemic models driven by stochastic algorithms with constant step. Discrete & Continuous Dynamical Systems - B, 2016, 21 (2) : 721-736. doi: 10.3934/dcdsb.2016.21.721
[8]

Manuela Caratozzolo, Santina Carnazza, Luigi Fortuna, Mattia Frasca, Salvatore Guglielmino, Giovanni Gurrieri, Giovanni Marletta. Self-organizing models of bacterial aggregation states. Mathematical Biosciences & Engineering, 2008, 5 (1) : 75-83. doi: 10.3934/mbe.2008.5.75
[9]

S. Mohamad, K. Gopalsamy. Neuronal dynamics in time varying enviroments: Continuous and discrete time models. Discrete & Continuous Dynamical Systems, 2000, 6 (4) : 841-860. doi: 10.3934/dcds.2000.6.841
[10]

Wendi Wang. Epidemic models with nonlinear infection forces. Mathematical Biosciences & Engineering, 2006, 3 (1) : 267-279. doi: 10.3934/mbe.2006.3.267
[11]

Carlos Castillo-Chavez, Baojun Song. Dynamical Models of Tuberculosis and Their Applications. Mathematical Biosciences & Engineering, 2004, 1 (2) : 361-404. doi: 10.3934/mbe.2004.1.361
[12]

Joshua E.S. Socolar. Discrete models of force chain networks. Discrete & Continuous Dynamical Systems - B, 2003, 3 (4) : 601-618. doi: 10.3934/dcdsb.2003.3.601
[13]

Radek Erban, Hyung Ju Hwang. Global existence results for complex hyperbolic models of bacterial chemotaxis. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1239-1260. doi: 10.3934/dcdsb.2006.6.1239
[14]

Dianmo Li, Zengxiang Gao, Zufei Ma, Baoyu Xie, Zhengjun Wang. Two general models for the simulation of insect population dynamics. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 623-628. doi: 10.3934/dcdsb.2004.4.623
[15]

Andriy Sokolov, Robert Strehl, Stefan Turek. Numerical simulation of chemotaxis models on stationary surfaces. Discrete & Continuous Dynamical Systems - B, 2013, 18 (10) : 2689-2704. doi: 10.3934/dcdsb.2013.18.2689
[16]

Zhimin Li, Tailei Zhang, Xiuqing Li. Threshold dynamics of stochastic models with time delays: A case study for Yunnan, China. Electronic Research Archive, 2021, 29 (1) : 1661-1679. doi: 10.3934/era.2020085
[17]

Francisco de la Hoz, Anna Doubova, Fernando Vadillo. Persistence-time estimation for some stochastic SIS epidemic models. Discrete & Continuous Dynamical Systems - B, 2015, 20 (9) : 2933-2947. doi: 10.3934/dcdsb.2015.20.2933
[18]

Yilei Tang, Dongmei Xiao, Weinian Zhang, Di Zhu. Dynamics of epidemic models with asymptomatic infection and seasonal succession. Mathematical Biosciences & Engineering, 2017, 14 (5&6) : 1407-1424. doi: 10.3934/mbe.2017073
[19]

Carlota Rebelo, Alessandro Margheri, Nicolas Bacaër. Persistence in some periodic epidemic models with infection age or constant periods of infection. Discrete & Continuous Dynamical Systems - B, 2014, 19 (4) : 1155-1170. doi: 10.3934/dcdsb.2014.19.1155
[20]

Jacky Cresson, Bénédicte Puig, Stefanie Sonner. Stochastic models in biology and the invariance problem. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2145-2168. doi: 10.3934/dcdsb.2016041

2018 Impact Factor: 1.313

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences