Discrete-Time Leap Method for Stochastic Simulation

• Autorzy: Rohr C.

Identyfikatory

DOI

10.3233/FI-2018-1680

• Języki publikacji: EN

Abstrakty

EN

We present an approach to improve the efficiency of stochastic simulation for large and dense biochemical reaction networks. We use stochastic Petri nets as modelling framework, but the proposed simulation approach is not limited to Petri net representations. The underlying continuous-time Markov chain (CTMC) is converted to an equivalent discrete-time Markov chain (DTMC); this itself gains no efficiency. We improve the efficiency via discrete-time leaps, even though this results in an approximate method. The discrete-time leaps are done by applying the maximum firing rule; this reduces drastically the number of steps. The presented algorithm is implemented in our modelling and simulation tool Snoopy, as well as in our advanced analysis and model checking tool MARCIE. We demonstrate the approach on models of different sizes and complexities.

Słowa kluczowe

EN

discrete-time leap method; stochastic Petri nets; approximate stochastic simulation; maximum firing rule; binomial distribution; weighted random shuffle

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 160, nr 1/2
• Strony: 181--198
• Opis fizyczny: Bibliogr. 25 poz., tab., wykr.

Twórcy

autor

Rohr C.

• Brandenburg University of Technology Cottbus-Senftenberg, Chair of Data Structures and Software Dependability, Postbox 1013 44, D-03013 Cottbus, Germany

Bibliografia

• [1] Oppenheim I, Shuler K, Weiss G. Stochastic and deterministic formulation of chemical rate equations. The Journal of Chemical Physics, 1969;50(1):460-466. URL http://dx.doi.org/10.1063/1.1670820.
• [2] Kurtz TG. The relationship between stochastic and deterministic models for chemical reactions. The Journal of Chemical Physics, 1972;57(7):2976-2978. URL http://dx.doi.org/10.1063/1.1678692.
• [3] Heiner M, Gilbert D. BioModel Engineering for Multiscale Systems Biology. Progress in Biophysics and Molecular Biology, 2013;111(2-3):119-128. URL https://doi.org/10.1016/j.pbiomolbio.2012.10.001.
• [4] Smallbone K, Mendes P. Large-scale metabolic models: From reconstruction to differential equations. Industrial Biotechnology, 2013;9(4):179-184. URL https://doi.org/10.1089/ind.2013.0003.
• [5] Rohr C. Simulative analysis of coloured extended stochastic Petri nets. Ph.D. thesis, BTU Cottbus-Senftenberg, Dep. of CS, 2017.
• [6] Gillespie D. A General Method for Numerically Simulating the Stochastic Time Evolution of Coupled Chemical Species. Journal of Computational Physics, 1976;22:403-434. doi:10.1016/0021-9991(76)90041-3.
• [7] Gillespie D. Exact stochastic simulation of coupled chemical reactions. The Journal of Physical Chemistry, 1977;81(25):2340-2361. doi:10.1021/j100540a008.
• [8] Gillespie DT. A rigorous derivation of the chemical master equation. Physica A: Statistical Mechanics and its Applications, 1992;188(1):404-425. URL https://doi.org/10.1016/0378-4371(92)90283-V.
• [9] Jensen A. Markoff chains as an aid in the study of Markoff processes. Scandinavian Actuarial Journal, 1953;1953(sup1):87-91.
• [10] Stewart W. Introduction to the Numerical Solution of Markov Chains. Princeton Univ. Press, 1994. ISBN:9780691036991.
• [11] Sandmann W. Brief Communication: Discrete-time stochastic modeling and simulation of biochemical networks. Comput. Biol. Chem., 2008;32:292-297. doi:10.1016/j.compbiolchem.2008.03.018.
• [12] Wilkinson D. Stochastic Modelling for System Biology. CRC Press, New York, 1st Edition, 2006. doi:10.1186/1475-925X-5-64.
• [13] Fisher RA, Yates F, et al. Statistical tables for biological, agricultural and medical research. Oliver and Boyd, Edinburgh, 6th edition, 1963. URL http://hdl.handle.net/2440/10701.
• [14] Durstenfeld R. Algorithm 235: Random Permutation. Commun. ACM, 1964;7(7):420. doi:10.1145/364520.364540.
• [15] Heiner M, Herajy M, Liu F, Rohr C, Schwarick M. Snoopy - a unifying Petri net tool. In: Proc. PETRI NETS 2012, volume 7347 of LNCS. Springer, 2012 pp. 398-407. doi:10.1007/978-3-642-31131-4_22.
• [16] Heiner M, Rohr C, Schwarick M. MARCIE - Model checking And Reachability analysis done effiCIEntly. In: Colom J, Desel J (eds.), Proc. PETRI NETS 2013, volume 7927 of LNCS. Springer, 2013 pp. 389-399. doi:10.1007/978-3-642-38697-8_21.
• [17] Cho KH, Shin SY, Kim HW, Wolkenhauer O, McFerran B, Kolch W. Mathematical modeling of the influence of RKIP on the ERK signaling pathway. In: Proc. CMSB 2003. LNCS 2602, Springer, 2003 pp. 127-141. doi:10.1007/3-540-36481-1_11.
• [18] Gilbert D, Heiner M. From Petri nets to differential equations - an integrative approach for biochemical network analysis. In: Proc. ICATPN 2006. LNCS 4024, Springer, 2006 pp. 181-200. doi:10.1007/11767589_11.
• [19] Heiner M, Donaldson R, Gilbert D. Petri Nets for Systems Biology, chapter 3, pp. 61-97. Jones & Bartlett Learning, LCC, 2010.
• [20] Levchenko A, Bruck J, Sternberg P. Scaffold proteins may biphasically affect the levels of mitogenactivated protein kinase signaling and reduce its threshold properties. Proc Natl Acad Sci USA, 2000;97(11):5818-5823.
• [21] Heiner M, Gilbert D, Donaldson R. Petri Nets in Systems and Synthetic Biology. In: SFM. LNCS 5016, Springer, 2008 pp. 215-264. doi:10.1007/978-3-540-68894-5_7.
• [22] Orth JD, Fleming RM, Palsson BO. Reconstruction and use of microbial metabolic networks: the core Escherichia coli metabolic model as an educational guide. EcoSal Plus, 2010;4(1). doi:10.1128/ecosalplus.10.2.1.
• [23] Erdrich P, Steuer R, Klamt S. An algorithm for the reduction of genome-scale metabolic network models to meaningful core models. BMC systems biology, 2015;9(1):48. doi:10.1186/s12918-015-0191-x.
• [24] Gilbert D, Heiner M. E.coli K-12 genome scale metabolic model. personal communication, 2016.
• [25] Monk JM, Charusanti P, Azizb RK, Lermand JA, Premyodhinb N, Orth JD, Feist AM, Palsson BO. Genome-scale metabolic reconstructions of multiple Escherichia coli strains highlight strain-specific adaptations to nutritional environments. PNAS, 2013;110(50):20338-20343. doi:10.1073/pnas.1307797110.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).