Generalizing Gillespie’s direct method to enable network-free simulations. (English) Zbl 1422.92062

Summary: Gillespie’s direct method for stochastic simulation of chemical kinetics is a staple of computational systems biology research. However, the algorithm requires explicit enumeration of all reactions and all chemical species that may arise in the system. In many cases, this is not feasible due to the combinatorial explosion of reactions and species in biological networks. Rule-based modeling frameworks provide a way to exactly represent networks containing such combinatorial complexity, and generalizations of Gillespie’s direct method have been developed as simulation engines for rule-based modeling languages. Here, we provide both a high-level description of the algorithms underlying the simulation engines, termed network-free simulation algorithms, and how they have been applied in systems biology research. We also define a generic rule-based modeling framework and describe a number of technical details required for adapting Gillespie’s direct method for network-free simulation. Finally, we briefly discuss potential avenues for advancing network-free simulation and the role they continue to play in modeling dynamical systems in biology.


92C42 Systems biology, networks
92C40 Biochemistry, molecular biology
92-04 Software, source code, etc. for problems pertaining to biology
Full Text: DOI arXiv Link


[1] Acar, M.; Mettetal, JT; Oudenaarden, A., Stochastic switching as a survival strategy in fluctuating environments, Nat Genet, 40, 471, (2008)
[2] Aitken, S.; Alexander, RD; Beggs, JD, A rule-based kinetic model of RNA polymerase II C-terminal domain phosphorylation, J R Soc Interface, 10, 20130438, (2013)
[3] Blake, WJ; Kærn, M.; Cantor, CR; Collins, JJ, Noise in eukaryotic gene expression, Nature, 422, 633, (2003)
[4] Blinov, ML; Faeder, JR; Goldstein, B.; Hlavacek, WS, A network model of early events in epidermal growth factor receptor signaling that accounts for combinatorial complexity, Biosystems (5th international conference on systems biology), 83, 136-151, (2006)
[5] Bortz, AB; Kalos, MH; Lebowitz, JL, A new algorithm for Monte Carlo simulation of Ising spin systems, J Comput Phys, 17, 10-18, (1975)
[6] Boutillier P, Ehrhard T, Krivine J (2017a) Incremental update for graph rewriting. In: Shao Z (ed) ESOP. Lecture notes in computer science, vol 4807 Berlin, pp 201-228 · Zbl 1485.68125
[7] Boutillier P, Feret J, Krivine J, Quyên LK (2017b) Kappa tools reference manual (v4.0rc1-9-g017c53207). https://github.com/Kappa-Dev/KaSim. Accessed 26 Mar 2018
[8] Bray, D., Molecular prodigality, Science, 299, 1189-1191, (2003)
[9] Cao, Y.; Terebus, A.; Liang, JIE, Accurate chemical master equation solution using multi-finite buffers, Multiscale Model Simul, 14, 923-963, (2016) · Zbl 1354.92033
[10] Chylek, LA; Akimov, V.; Dengjel, J.; Rigbolt, KTG; Hu, B.; Hlavacek, WS; Blagoev, B., Phosphorylation site dynamics of early T-cell receptor signaling, PLoS ONE, 9, e104240, (2014)
[11] Chylek, LA; Harris, LA; Tung, CS; Faeder, JR; Lopez, CF; Hlavacek, WS, Rule-based modeling: a computational approach for studying biomolecular site dynamics in cell signaling systems, WIRES Syst Biol Med, 6, 13-36, (2014)
[12] Colvin, J.; Monine, MI; Faeder, JR; Hlavacek, WS; Hoff, DDV; Posner, RG, Simulation of large-scale rule-based models, Bioinformatics, 25, 910-917, (2009)
[13] Colvin, J.; Monine, MI; Gutenkunst, RN; Hlavacek, WS; Hoff, DDV; Posner, RG, RuleMonkey: software for stochastic simulation of rule-based models, BMC Bioinform, 11, 404, (2010)
[14] Cox D, Miller H (1965) The theory of stochastic processes. Methuen, London · Zbl 0149.12902
[15] Creamer, MS; Stites, EC; Aziz, M.; Cahill, JA; Tan, CW; Berens, ME; Han, H.; Bussey, KJ; Hoff, DD; Hlavacek, WS; Posner, RG, Specification, annotation, visualization and simulation of a large rule-based model for ERBB receptor signaling, BMC Syst Biol, 6, 1, (2012)
[16] Danos, V.; Laneve, C., Formal molecular biology, Theor Comput Sci, 325, 69-110, (2004) · Zbl 1071.68041
[17] Danos V, Feret J, Fontana W, Harmer R, Krivine J (2007a) Rule-based modelling of cellular signalling. In: Caires L, Vasconcelos VT (eds) CONCUR 2007—concurrency theory. Lecture notes in computer science, vol 4703. Springer, Berlin, pp 17-41 · Zbl 1151.68723
[18] Danos V, Feret J, Fontana W, Krivine J (2007b) Scalable simulation of cellular signaling networks. In: Shao Z (ed) Programming languages and systems. APLAS. Lecture notes in computer science, vol 4807. Springer, Berlin, pp 139-157
[19] Danos V, Feret J, Fontana W, Harmer R, Krivine J (2008) Rule-based modelling, symmetries, refinements. In: Fisher J (ed) Formal methods in systems biology. Lecture notes in computer science, vol 5054. Springer, Berlin, pp 103-122 · Zbl 1348.92070
[20] Danos, V.; Feret, J.; Fontana, W.; Harmer, R.; Krivine, J.; Priami, C. (ed.); Back, RJ (ed.); Petre, I. (ed.), Rule-based modelling and model perturbation, 116-137, (2009), Berlin
[21] Oliveira, Luís P.; Damien, Hudebine; Denis, Guillaume; Verstraete Jan, J., A review of kinetic modeling methodologies for complex processes, Oil Gas Sci Technol, 71, 45, (2016)
[22] Deeds, EJ; Krivine, J.; Feret, J.; Danos, V.; Fontana, W., Combinatorial complexity and compositional drift in protein interaction networks, PLoS ONE, 7, e32032, (2012)
[23] Deuflhard P, Röblitz S (2015) ODE models for systems biological networks. A guide to numerical modelling in systems biology. Springer, Cham, pp 1-32 · Zbl 1325.92001
[24] Elowitz, MB; Siggia, ED; Levine, AJ; Swain, PS, Stochastic gene expression in a single cell, Science, 297, 1183-1187, (2002)
[25] Endy, D.; Brent, R., Modelling cellular behaviour, Nature, 409, 391-395, (2001)
[26] Faeder, JR; Blinov, ML; Goldstein, B.; Hlavacek, WS, Combinatorial complexity and dynamical restriction of network flows in signal transduction, Syst Biol, 2, 5-15, (2005)
[27] Faeder, JR; Blinov, ML; Goldstein, B.; Hlavacek, WS, Rule-based modeling of biochemical networks, Complexity, 10, 22-41, (2005)
[28] Faeder, JR; Blinov, ML; Hlavacek, WS; Maly, IV (ed.), Rule-based modeling of biochemical systems with bionetgen, 113-167, (2009), Totowa, NJ
[29] Faulon, JL; Sault, AG, Stochastic generator of chemical structure. 3. Reaction network generation, J Chem Inf Comp Sci, 41, 894-908, (2001)
[30] Fermi E, Richtmyer R (1948) Note on census-taking in Monte Carlo calculations. Technical Report (AECD-3164; LADC-946)
[31] Gibson, MA; Bruck, J., Efficient exact stochastic simulation of chemical systems with many species and many channels, J Phys Chem A, 104, 1876-1889, (2000)
[32] Gillespie, DT, A general method for numerically simulating the stochastic time evolution of coupled chemical reactions, J Comput Phys, 22, 403-434, (1976)
[33] Gillespie, DT; etal., Exact stochastic simulation of coupled chemical reactions, J Phys Chem, 81, 2340-2361, (1977)
[34] Goldstein, B.; Perelson, AS, Equilibrium theory for the clustering of bivalent cell surface receptors by trivalent ligands. Application to histamine release from basophils, Biophys J, 45, 1109-1123, (1984)
[35] Harmer, R.; Danos, V.; Feret, J.; Krivine, J.; Fontana, W., Intrinsic information carriers in combinatorial dynamical systems, Chaos, 20, 1-16, (2010) · Zbl 1311.92202
[36] Hufton, PG; Lin, YT; Galla, T.; McKane, AJ, Intrinsic noise in systems with switching environments, Phys Rev E, 93, 052119, (2016)
[37] IUPAC (1997) Compendium of chemical terminology (the “Gold Book”), 2nd ed. Blackwell Scientific Publications, Oxford
[38] Kærn, M.; Elston, TC; Blake, WJ; Collins, JJ, Stochasticity in gene expression: from theories to phenotypes, Nat Rev Genet, 6, 451, (2005)
[39] Kepler, TB; Elston, TC, Stochasticity in transcriptional regulation: origins, consequences, and mathematical representations, Biophys J, 81, 3116-3136, (2001)
[40] Klann, M.; Koeppl, H., Spatial simulations in systems biology: from molecules to cells, Int J Mol Sci, 13, 7798-7827, (2012)
[41] Kochańczyk, M.; Hlavacek, WS; Lipniacki, T., Spatkin: a simulator for rule-based modeling of biomolecular site dynamics on surfaces, Bioinformatics, 33, 3667-3669, (2017)
[42] Köhler, A.; Krivine, J.; Vidmar, J.; Mendes, P. (ed.); Dada, JO (ed.); Smallbone, K. (ed.), A rule-based model of base excision repair, No. 8859, 173-195, (2014), Cham
[43] Kühn, C.; Hillmann, K., Rule-based modeling of labor market dynamics: an introduction, J Econ Interact Coor, 11, 57-76, (2016)
[44] Novère, N.; Shimizu, TS, STOCHSIM: modelling of stochastic biomolecular processes, Bioinformatics, 17, 575-576, (2001)
[45] Novère, N.; Bornstein, B.; Broicher, A.; Courtot, M.; Donizelli, M.; Dharuri, H.; Li, L.; Sauro, H.; Schilstra, M.; Shapiro, B.; etal., Biomodels database: a free, centralized database of curated, published, quantitative kinetic models of biochemical and cellular systems, Nucleic Acids Res, 34, d689-d691, (2006)
[46] Lin YT, Buchler NE (2017) Efficient analysis of stochastic gene dynamics in the non-adiabatic regime using piecewise deterministic Markov processes. ArXiv preprint arXiv:1710.09452
[47] Lin, YT; Doering, CR, Gene expression dynamics with stochastic bursts: construction and exact results for a coarse-grained model, Phys Rev E, 93, 022409, (2016)
[48] Lin, YT; Galla, T., Bursting noise in gene expression dynamics: linking microscopic and mesoscopic models, J R Soc Interface, 13, 20150772, (2016)
[49] Lin YT, Hufton PG, Lee EJ, Potoyan DA (2017) A stochastic and dynamical view of pluripotency in mouse embryonic stem cells. ArXiv preprint arXiv:1710.08542
[50] Lok, L.; Brent, R., Automatic generation of cellular reaction networks with Moleculizer 1.0, Nat Biotechnol, 23, 131-136, (2005)
[51] Mayer, BJ; Blinov, ML; Loew, LM, Molecular machines or pleiomorphic ensembles: signaling complexes revisited, J Biol, 8, 81, (2009)
[52] Metropolis, N.; Ulam, S., The Monte Carlo method, J Am Stat Assoc, 44, 335-341, (1949) · Zbl 0033.28807
[53] Metropolis, N.; Rosenbluth, AW; Rosenbluth, MN; Teller, AH; Teller, E., Equation of state calculations by fast computing machines, J Chem Phys, 21, 1087-1092, (1953)
[54] Munsky, B.; Khammash, M., The finite state projection algorithm for the solution of the chemical master equation, J Chem Phys, 124, 044104, (2006) · Zbl 1131.82020
[55] Munsky, B.; Trinh, B.; Khammash, M., Listening to the noise: random fluctuations reveal gene network parameters, Mol Syst Biol, 5, 318, (2009)
[56] Nag, A.; Monine, MI; Faeder, JR; Goldstein, B., Aggregation of membrane proteins by cytosolic cross-linkers: theory and simulation of the LAT-Grb2-SOS1 system, Biophys J, 96, 2604-2623, (2009)
[57] Nag, A.; Faeder, JR; Goldstein, B., Shaping the response: the role of Fc \(\epsilon\) RI and Syk expression levels in mast cell signalling, IET Syst Biol, 4, 334-47, (2010)
[58] Ozbudak, EM; Thattai, M.; Kurtser, I.; Grossman, AD; Oudenaarden, A., Regulation of noise in the expression of a single gene, Nat Genet, 31, 69, (2002)
[59] Ramaswamy, R.; Sbalzarini, IF, A partial-propensity variant of the composition-rejection stochastic simulation algorithm for chemical reaction networks, J Chem Phys, 132, 044102, (2010)
[60] Sneddon, MW; Faeder, JR; Emonet, T., Efficient modeling, simulation and coarse-graining of biological complexity with NFsim, Nat Methods, 8, 177-183, (2011)
[61] Sorokina, O.; Sorokin, A.; Douglas Armstrong, J.; Danos, V., A simulator for spatially extended kappa models, Bioinformatics, 29, 3105-3106, (2013)
[62] Stites, EC; Aziz, M.; Creamer, MS; Hoff, DD; Posner, RG; Hlavacek, WS, Use of mechanistic models to integrate and analyze multiple proteomic datasets, Biophys J, 108, 1819-1829, (2015)
[63] Su, X.; Ditlev, JA; Hui, E.; Xing, W.; Banjade, S.; Okrut, J.; King, DS; Taunton, J.; Rosen, MK; Vale, RD, Phase separation of signaling molecules promotes T cell receptor signal transduction, Science, 352, 595-599, (2016)
[64] Suderman, R.; Deeds, EJ, Machines vs. ensembles: effective MAPK signaling through heterogeneous sets of protein complexes, PLoS Comput Biol, 9, e1003278, (2013)
[65] Suderman R, Hlavacek WS (2017) TRuML: a translator for rule-based modeling languages. In: Proceedings of the 8th ACM international conference on bioinformatics, computational biology, and health informatics. ACM, New York, ACM-BCB ’17, pp 372-377
[66] Sweeney, B.; Zhang, T.; Schwartz, R., Exploring the parameter space of complex self-assembly through virus capsid models, Biophys J, 94, 772-783, (2008)
[67] Tapia Valenzuela JJ (2016) A study on systems modeling frameworks and their interoperability. Ph.D. thesis, University of Pittsburgh
[68] Thattai, M.; Oudenaarden, A., Stochastic gene expression in fluctuating environments, Genetics, 167, 523-530, (2004)
[69] Voter, AF; Sickafus, KE (ed.); Kotomin, EA (ed.); Uberuaga, BP (ed.), Introduction to the kinetic Monte Carlo method, 1-23, (2007), Dordrecht
[70] Yang, J.; Hlavacek, WS, The efficiency of reactant site sampling in network-free simulation of rule-based models for biochemical systems, Phys Biol, 8, 055009, (2011)
[71] Yang, J.; Monine, MI; Faeder, JR; Hlavacek, WS, Kinetic Monte Carlo method for rule-based modeling of biochemical networks, Phys Rev E, 78, 910, (2008)
[72] Young, W.; Elcock, E., Monte carlo studies of vacancy migration in binary ordered alloys: I, Proc Phys Soc, 89, 735, (1966)
[73] Zhang T, Rohlfs R, Schwartz R (2005) Implementation of a discrete event simulator for biological self-assembly systems. In: Proceedings of the 37th conference on winter simulation, winter simulation conference, WSC ’05, pp 2223-2231
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.