×

Accurate chemical master equation solution using multi-finite buffers. (English) Zbl 1354.92033

Summary: The discrete chemical master equation (dCME) provides a fundamental framework for studying stochasticity in mesoscopic networks. Because of the multiscale nature of many networks where reaction rates have a large disparity, directly solving dCMEs is intractable due to the exploding size of the state space. It is important to truncate the state space effectively with quantified errors, so accurate solutions can be computed. It is also important to know if all major probabilistic peaks have been computed. Here we introduce the accurate CME (ACME) algorithm for obtaining direct solutions to dCMEs. With multifinite buffers for reducing the state space by \(O(n!)\), exact steady-state and time-evolving network probability landscapes can be computed. We further describe a theoretical framework of aggregating microstates into a smaller number of macrostates by decomposing a network into independent aggregated birth and death processes and give an a priori method for rapidly determining steady-state truncation errors. The maximal sizes of the finite buffers for a given error tolerance can also be precomputed without costly trial solutions of dCMEs. We show exactly computed probability landscapes of three multiscale networks, namely, a 6-node toggle switch, 11-node phage-lambda epigenetic circuit, and 16-node MAPK cascade network, the latter two with no known solutions. We also show how probabilities of rare events can be computed from first-passage times, another class of unsolved problems challenging for simulation-based techniques due to large separations in time scales. Overall, the ACME method enables accurate and efficient solutions of the dCME for a large class of networks.

MSC:

92C45 Kinetics in biochemical problems (pharmacokinetics, enzyme kinetics, etc.)
92C40 Biochemistry, molecular biology
92-08 Computational methods for problems pertaining to biology

Software:

ARPACK; Expokit
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R.J. Allen, P.B. Warren, and P.R. Ten Wolde, {\it Sampling rare switching events in biochemical networks}, Phys. Rev. Lett., 94 (2005), 18104.
[2] R.J. Allen, C. Valeriani, and P.R. ten Wolde, {\it Forward flux sampling for rare event simulations}, J. Phys., 21 (2009), 463102.
[3] P. Ao, {\it Laws in Darwinian evolutionary theory}, Phys. Life Rev., 2 (2005), pp. 117-156.
[4] P. Ao, D. Galas, L. Hood, L. Yin, and X.M. Zhu, {\it Towards predictive stochastic dynamical modeling of cancer genesis and progression}, Interdiscip. Sci. Comput. Life Sci., 2 (2010), pp. 140-144.
[5] A. Arkin, J. Ross, and H.H. McAdams, {\it Stochastic kinetic analysis of developmental pathway bifurcation in phage \(λ\)-infected Escherichia coli cells}, Genetics, 149 (1998), pp. 1633-1648.
[6] E. Aurell, S. Brown, J. Johanson, and K. Sneppen, {\it Stability puzzles in phage \(λ\)}, Phys. Rev. E, 65 (2002), 051914.
[7] E. Aurell and K. Sneppen, {\it Epigenetics as a first exit problem}, Phys. Rev. Lett., 88 (2002), 048101.
[8] D.A. Beard and H. Qian, {\it Chemical Biophysics: Quantitative Analysis of Cellular Systems}, Cambridge University Press, Cambridge, 2008. · Zbl 1320.92001
[9] Y. Cao and J. Liang, {\it Optimal enumeration of state space of finitely buffered stochastic molecular networks and exact computation of steady state landscape probability}, BMC Syst. Biol., 2 (2008), 30.
[10] Y. Cao and J. Liang, {\it Adaptively biased sequential importance sampling for rare events in reaction networks with comparison to exact solutions from finite buffer dCME method}, J. Chem. Phys., 139 (2013), 025101.
[11] Y. Cao, H.-M. Lu, and J. Liang, {\it Probability landscape of heritable and robust epigenetic state of lysogeny in phage lambda}, Proc. Natl. Acad. Sci. USA, 107 (2010), pp. 18445-18450.
[12] Y. Cao, A. Terebus, and J. Liang, {\it State space truncation with quantified errors for accurate solutions to discrete chemical master equation}, Bull. Math. Biol., 78 (2016), pp. 617-661. · Zbl 1341.92086
[13] F.R.K. Chung, {\it Spectral Graph Theory}, Vol. 92, AMS, Providence, RI, 1997. · Zbl 0867.05046
[14] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, et al., {\it Introduction to Algorithms}, Vol. 2, MIT Press, Cambridge, MA, 2001. · Zbl 1047.68161
[15] B.J. Daigle, M.K. Roh, D.T. Gillespie, and L.R. Petzold, {\it Automated estimation of rare event probabilities in biochemical systems}, J. Chem. Phys., 134 (2011), 044110.
[16] I.G. Darvey, B.W. Ninham, and P.J. Staff, {\it Stochastic models for second order chemical reaction kinetics. The equilibrium state}, J. Chem. Phys., 45 (1966), pp. 2145-2155.
[17] P. Deuflhard, W. Huisinga, T. Jahnke, and M. Wulkow, {\it Adaptive discrete Galerkin methods applied to the chemical master equation}, SIAM J. Sci. Comput., 30 (2008), pp. 2990-3011. · Zbl 1178.41003
[18] R.M. Donovan, A.J. Sedgewick, J.R. Faeder, and D.M. Zuckerman, {\it Efficient stochastic simulation of chemical kinetics networks using a weighted ensemble of trajectories}, J. Chem. Phys., 139 (2013), 115105.
[19] M.B. Elowitz, A.J. Levine, E.D. Siggia, and P.S. Swain, {\it Stochastic gene expression in a single cell}, Science, 297 (2002), pp. 1183-1186.
[20] B.L. Fox and P.W. Glynn, {\it Computing Poisson probabilities}, Commun. ACM, 31 (1988), pp. 440-445.
[21] C.W. Gardiner, {\it Handbook of Stochastic Methods for Physics, Chemistry and the Natural Sciences}, Springer, New York, 2004. · Zbl 1143.60001
[22] T.S. Gardner, C.R. Cantor, and J.J. Collins, {\it Construction of a genetic toggle switch in Escherichia coli}, Nature, 403 (2000), pp. 339-342.
[23] D.T. Gillespie, {\it Exact stochastic simulation of coupled chemical reactions}, J. Phys. Chem., 81 (1977), pp. 2340-2361.
[24] D.T. Gillespie, {\it A rigorous derivation of the chemical master equation}, Phys. A, 188 (1992), pp. 404-425.
[25] D.T. Gillespie, {\it The chemical Langevin equation}, J. Chem. Phys., 113 (2000), pp. 297-306.
[26] D.T. Gillespie, {\it The chemical Langevin and Fokker-Planck equations for the reversible isomerization reaction}, J. Phys. Chem. A, 106 (2002), pp. 5063-5071.
[27] D.T. Gillespie, {\it A diffusional bimolecular propensity function}, J. Chem. Phys., 131 (2009), 164109.
[28] D.T. Gillespie, M. Roh, and L.R. Petzold, {\it Refining the weighted stochastic simulation algorithm}, J. Chem. Phys., 130 (2009), 174103.
[29] R. Grima, P. Thomas, and A.V. Straube, {\it How accurate are the nonlinear chemical Fokker-Planck and chemical Langevin equations?}, J. Chem. Phys., 135 (2011), 084103.
[30] D. Gross and D.R. Miller, {\it The randomization technique as a modeling tool and solution procedure for transient Markov processes}, Oper. Res., 32 (1984), pp. 343-361. · Zbl 0536.60078
[31] D. Hanahan and R.A. Weinberg, {\it The hallmarks of cancer}, Cell, 100 (2000), pp. 57-70.
[32] E.L. Haseltine and J.B. Rawlings, {\it Approximate simulation of coupled fast and slow reactions for stochastic chemical kinetics}, J. Chem. Phys., 117 (2002), pp. 6959-6969.
[33] D. Hawley and W. McClure, {\it In vitro comparison of initiation properties of bacteriophage lambda wild-type PR and x3 mutant promoters}, Proc. Natl. Acad. Sci. USA, 77 (1980), pp. 6381-6385.
[34] D. Hawley and W. McClure, {\it Mechanism of activation of transcription initiation from the lambda PRM promoter}, J. Molecular Biol., 157 (1982), pp. 493-525.
[35] C.-Y. Huang and J.E. Ferrell, {\it Ultrasensitivity in the mitogen-activated protein kinase cascade}, Proc. Natl. Acad. Sci. USA, 93 (1996), pp. 10078-10083.
[36] A. Irle, {\it Stochastic ordering for continuous-time processes}, J. Appl. Probab., (2003), pp. 361-375. · Zbl 1031.60016
[37] T. Jahnke, {\it On reduced models for the chemical master equation}, Multiscale Model. Simul., 9 (2011), pp. 1646-1676. · Zbl 1244.65005
[38] S. Jiao, Y. Wang, B. Yuan, and P. Ao, {\it Kinetics of Muller’s ratchet from adaptive landscape viewpoint}, in Proceedings of the IEEE International Conference on Systems Biology (ISB), 2011, IEEE, 2011, pp. 27-32.
[39] G.L. Johnson and R. Lapadat, {\it Mitogen-activated protein kinase pathways mediated by erk, jnk, and p38 protein kinases}, Science, 298 (2002), pp. 1911-1912.
[40] V. Kazeev, M. Khammash, M. Nip, and C. Schwab, {\it Direct solution of the chemical master equation using quantized tensor trains}, PLoS Comput. Biol., 10 (2014), e1003359.
[41] T.B. Kepler and T.C. Elston, {\it Stochasticity in transcriptional regulation: Origins, consequences, and mathematical representations}, Biophys. J., 81 (2001), pp. 3116-3136.
[42] H. Kim and E. Gelenbe, {\it Stochastic gene expression modeling with Hill function for switch-like gene responses}, IEEE/ACM Trans. Comput. Biol. Bioinform., 9 (2012), pp. 973-979.
[43] K.-Y. Kim and J. Wang, {\it Potential energy landscape and robustness of a gene regulatory network: Toggle switch}, PLoS Comput. Biol., 3 (2007), e60.
[44] C. Kuttler and J. Niehren, {\it Gene regulation in the pi calculus: Simulating cooperativity at the lambda switch}, Trans. Comput. Syst. Biol. VII, 4230 (2006), pp. 24-55.
[45] H. Kuwahara and I. Mura, {\it An efficient and exact stochastic simulation method to analyze rare events in biochemical systems}, J. Chem. Phys., 129 (2008), 165101.
[46] I.J. Laurenzi, {\it An analytical solution of the stochastic master equation for reversible bimolecular reaction kinetics}, J. Chem. Phys., 113 (2000), pp. 3315-3322.
[47] R. Lehoucq, D. Sorensen, and C. Yang, {\it Arpack Users’ Guide: Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods}, SIAM, Philadelphia, 1998. · Zbl 0901.65021
[48] M. Li, W. McClure, and M. Susskind, {\it Changing the mechanism of transcriptional activation by phage lambda repressor}, Proc. Natl. Acad. Sci. USA, 94 (1997), pp. 3691-3696.
[49] J.W. Little, D.P. Shepley, and D.W. Wert, {\it Robustness of a gene regulatory circuit}, EMBO Journal, 18 (1999), pp. 4299-4307.
[50] M. Maggioni, T. Berger-Wolf, and J. Liang, {\it GPU-based steady-state solution of the chemical master equation}, in Proceedings of the 27th International, Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), IEEE, 2013, pp. 579-588.
[51] N.I. Markevich, J.B. Hoek, and B.N. Kholodenko, {\it Signaling switches and bistability arising from multisite phosphorylation in protein kinase cascades}, J. Cell Biol., 164 (2004), pp. 353-359.
[52] H.H. McAdams and A. Arkin, {\it It’s a noisy business! Genetic regulation at the nanomolar scale}, Trends Genet., 15 (1999), pp. 65-69.
[53] D.A. McQuarrie, {\it Stochastic approach to chemical kinetics}, J. Appl. Probab., 4 (1967), pp. 413-478. · Zbl 0231.60090
[54] R. Merris, {\it Laplacian matrices of graphs: A survey}, Linear Algebra Appl., 197 (1994), pp. 143-176. · Zbl 0802.05053
[55] B. Munsky and M. Khammash, {\it The finite state projection algorithm for the solution of the chemical master equation}, J. Chem. Phys., 124 (2006), 044104. · Zbl 1131.82020
[56] B. Munsky and M. Khammash, {\it A multiple time interval finite state projection algorithm for the solution to the chemical master equation}, J. Comput. Phys., 226 (2007), pp. 818-835. · Zbl 1131.82020
[57] B. Munsky and M. Khammash, {\it The finite state projection approach for the analysis of stochastic noise in gene networks}, IEEE Trans. Automat. Control, 53 (2008), pp. 201-214. · Zbl 1366.92049
[58] M. Ptashne, {\it A Genetic Switch: Phage Lambda Revisited}, 3rd ed., Cold Spring Harbor Laboratory Press, Cold Spring Harbor, NY, 2004.
[59] H. Qian, {\it Cooperativity in cellular biochemical processes: Noise-enhanced sensitivity, fluctuating enzyme, bistability with nonlinear feedback, and other mechanisms for sigmoidal responses}, Ann. Rev. Biophys., 41 (2012), pp. 179-204.
[60] L. Qiao, R.B. Nachbar, I.G. Kevrekidis, and S.Y. Shvartsman, {\it Bistability and oscillations in the Huang-Ferrell model of MAPK signaling}, PLoS Comput. Biol., 3 (2007), e184.
[61] M.K. Roh, B.J. Daigle, D.T. Gillespie, and L.R. Petzold, {\it State-dependent doubly weighted stochastic simulation algorithm for automatic characterization of stochastic biochemical rare events}, J. Chem. Phys., 135 (2011), 234108.
[62] Y. Saad and M.H. Schultz, {\it GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems}, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856-869. · Zbl 0599.65018
[63] M. Santillán, {\it On the use of the Hill functions in mathematical models of gene regulatory networks}, Math. Model. Nat. Phenom., 3 (2008), pp. 85-97. · Zbl 1337.92082
[64] D. Schultz, J.N. Onuchic, and P.G. Wolynes, {\it Understanding stochastic simulations of the smallest genetic networks}, J. Chem. Phys., 126 (2007), 245102.
[65] M.A. Shea and G.K. Ackers, {\it The \(OR\) control system of bacteriophage lambda a physical-chemical model for gene regulation}, J. Mol. Biol., 181 (1985), pp. 211-230.
[66] J. Shi, T. Chen, R. Yuan, B. Yuan, and P. Ao, {\it Relation of a new interpretation of stochastic differential equations to Ito process}, J. Stat. Phys., 148 (2012), pp. 579-590. · Zbl 1251.82043
[67] R.B. Sidje, {\it Expokit: A software package for computing matrix exponentials}, ACM Trans. Math. Software, 24 (1998), pp. 130-156. · Zbl 0917.65063
[68] P. Sjöberg, P. Lötstedt, and J. Elf, {\it Fokker-Planck approximation of the master equation in molecular biology}, Comput. Vis. Sci., 12 (2009), pp. 37-50.
[69] P. Smolen, D.A. Baxter, and J.H. Byrne, {\it Bistable MAP kinase activity: A plausible mechanism contributing to maintenance of late long-term potentiation}, American J. Phys. Cell Phys., 294 (2008), pp. C503-C515.
[70] W.J. Stewart, {\it Introduction to the Numerical Solution of Markov Chains}, Princeton University Press, Princeton, NJ, 1994. · Zbl 0821.65099
[71] J. Stewart-Ornstein and H. El-Samad, {\it Stochastic modeling of cellular networks}, Comput. Methods Cell Biol., 110 (2012), pp. 111-137.
[72] P.S. Swain, M.B. Elowitz, and E.D. Siggia, {\it Intrinsic and extrinsic contributions to stochasticity in gene expression}, Proc. Natl. Acad. Sci. USA, 99 (2002), pp. 12795-12800.
[73] H.M. Taylor and S. Karlin, {\it An Introduction to Stochastic Modeling}, 3rd ed., Academic Press, New York, 1998. · Zbl 0946.60002
[74] P. Thomas, H. Matuschek, and R. Grima, {\it How reliable is the linear noise approximation of gene regulatory networks?}, BMC Genomics, 14 (2013), S5.
[75] L. Truffet, {\it Near complete decomposability: Bounding the error by a stochastic comparison method}, Adv. Appl. Probab., 29 (1997), pp. 830-855. · Zbl 0892.60101
[76] N.G. Van Kampen, {\it Stochastic processes in physics and chemistry}, 3rd ed., Elsevier Science and Technology Books, New York, 2007. · Zbl 0974.60020
[77] N.G. Van Kampen, {\it A power series expansion of the master equation}, Canad. J. Phys., 39 (1961), pp. 551-567. · Zbl 0108.42902
[78] M. Vellela and H. Qian, {\it A quasistationary analysis of a stochastic chemical reaction: Keizer’s paradox}, Bull. Math. Biol., 69 (2007), pp. 1727-1746. · Zbl 1298.92129
[79] G. Wang, X. Zhu, J. Gu, and P. Ao, {\it Quantitative implementation of the endogenous molecular-cellular network hypothesis in hepatocellular carcinoma}, Interface Focus, 4 (2014), 20130064.
[80] X. Wang, N. Hao, H.G. Dohlman, and T.C. Elston, {\it Bistability, stochasticity, and oscillations in the mitogen-activated protein kinase cascade}, Biophys. J., 90 (2006), pp. 1961-1978.
[81] D.J. Wilkinson, {\it Stochastic modelling for quantitative description of heterogeneous biological systems}, Nat. Rev. Genet., 10 (2009), pp. 122-133.
[82] V. Wolf, R. Goel, M. Mateescu, and T. Henzinger, {\it Solving the chemical master equation using sliding windows}, BMC Syst. Biol., 4 (2010), 42.
[83] X.-M. Zhu, L. Yin, L. Hood, and P. Ao, {\it Calculating biological behaviors of epigenetic states in the phage \(λ\) life cycle}, Funct. Int. Genomics, 4 (2004), pp. 188-195.
[84] X.-M. Zhu, L. Yin, L. Hood, and P. Ao, {\it Robustness, stability and efficiency of phage lambda genetic switch: Dynamical structure analysis}, J. Bioinform. Comput. Biol., 2 (2004), pp. 785-817.
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.