65 research outputs found
Krylov and steady-state techniques for the solution of the chemical master equation for the mitogen-activated protein kinase cascade
No full textStochastic chemical kinetics and the total quasi-steady-state assumption: Application to the stochastic simulation algorithm and chemical master equation
No full textRecently the application of the quasi-steady-state approximation QSSA to the stochastic simulation algorithm SSA was suggested for the purpose of speeding up stochastic simulations of chemical systems that involve both relatively fast and slow chemical reactions Rao and Arkin, J.Chem. Phys. 118, 4999 2003 and further work has led to the nested and slow-scale SSA. Improved numerical efficiency is obtained by respecting the vastly different time scales characterizing the system and then by advancing only the slow reactions exactly, based on a suitable approximation to the fast reactions. We considerably extend these works by applying the QSSA to numerical methods for the direct solution of the chemical master equation CME and, in particular, to the finite state projection algorithm Munsky and Khammash, J. Chem. Phys. 124, 044104 2006, in conjunction with Krylov methods. In addition, we point out some important connections to the literature on the deterministic total QSSA tQSSA and place the stochastic analogue of the QSSA within the more general framework of aggregation of Markov processes. We demonstrate the new methods on four examples: Michaelis–Menten enzyme kinetics, double phosphorylation, the Goldbeter–Koshland switch, and the mitogen activated protein kinase cascade. Overall, we report dramatic improvements by applying the tQSSA to the CME solver
Stochastic modelling of T cell homeostasis for two competing clonotypes via the master equation
No full textStochastic models for competing clonotypes of T cells by multivariate, continuous-time, discrete state, Markov processes have been proposed in the literature by Stirk, Molina-París and van den Berg (2008). A stochastic modelling framework is important because of rare events associated with small populations of some critical cell types. Usually, computational methods for these problems employ a trajectory-based approach, based on Monte Carlo simulation. This is partly because the complementary, probability density function (PDF) approaches can be expensive but here we describe some efficient PDF approaches by directly solving the governing equations, known as the Master Equation. These computations are made very efficient through an approximation of the state space by the Finite State Projection and through the use of Krylov subspace methods when evolving the matrix exponential. These computational methods allow us to explore the evolution of the PDFs associated with these stochastic models, and bimodal distributions arise in some parameter regimes. Time-dependent propensities naturally arise in immunological processes due to, for example, age-dependent effects. Incorporating time-dependent propensities into the framework of the Master Equation significantly complicates the corresponding computational methods but here we describe an efficient approach via Magnus formulas. Although this contribution focuses on the example of competing clonotypes, the general principles are relevant to multivariate Markov processes and provide fundamental techniques for computational immunology
Simulation of bimolecular reactions: Numerical challenges with the graph Laplacian
No full textAn important framework for modelling and simulation of chemical reactions is a Markov process sometimes known as a master equation. Explicit solutions of master equations are rare; in general the explicit solution of the governing master equation for a bimolecular reaction remains an open question. We show that a solution is possible in special cases. One method of solution is diagonalization. The crucial class of matrices that describe this family of models are non-symmetric graph Laplacians. We illustrate how standard numerical algorithms for finding eigenvalues fail for the non-symmetric graph Laplacians that arise in master equations for models of chemical kinetics. We propose a novel way to explore the pseudospectra of the non-symmetric graph Laplacians that arise in this class of applications, and illustrate our proposal by Monte Carlo. Finally, we apply the Magnus expansion, which provides a method of simulation when rates change in time. Again the graph Laplacian structure presents some unique issues: standard numerical methods of more than second-order fail to preserve positivity. We therefore propose a method that achieves fourth-order accuracy, and maintain positivity.
References
A. Basak, E. Paquette, and O. Zeitouni. Regularization of non-normal matrices by gaussian noise–-the banded toeplitz and twisted toeplitz cases. In Forum of Mathematics, Sigma, volume 7. Cambridge University Press, 2019. doi:10.1017/fms.2018.29.
S. Blanes, F. Casas, J. A. Oteo, and J. Ros. The magnus expansion and some of its applications. Phys. Rep., 470(5-6):151–238, 2009. doi:10.1016/j.physrep.2008.11.001.
B. A. Earnshaw and J. P. Keener. Invariant manifolds of binomial-like nonautonomous master equations. SIAM J. Appl. Dyn. Sys., 9(2):568–588, 2010. doi10.1137/090759689.
J. Gunawardena. A linear framework for time-scale separation in nonlinear biochemical systems. PloS One, 7(5):e36321, 2012. doi:10.1371/journal.pone.0036321.
A. Iserles and S. MacNamara. Applications of magnus expansions and pseudospectra to markov processes. Euro. J. Appl. Math., 30(2):400–425, 2019. doi:10.1017/S0956792518000177.
S. MacNamara. Cauchy integrals for computational solutions of master equations. ANZIAM Journal, 56:32–51, 2015. doi:10.21914/anziamj.v56i0.9345.
S. MacNamara, A. M. Bersani, K. Burrage, and R. B. Sidje. Stochastic chemical kinetics and the total quasi-steady-state assumption: Application to the stochastic simulation algorithm and chemical master equation. J. Chem. Phys., 129:095105, 2008. doi:10.1063/1.2971036.
S. MacNamara and K. Burrage. Stochastic modeling of naive T cell homeostasis for competing clonotypes via the master equation. SIAM Multiscale Model. Sim., 8(4):1325–1347, 2010.
S. MacNamara, K. Burrage, and R. B. Sidje. Multiscale modeling of chemical kinetics via the master equation. SIAM Multiscale Model. and Sim., 6(4):1146–1168, 2008. doi:10.1137/060678154.
S. MacNamara, Wi. McLean, and K. Burrage. Wider contours and adaptive contours, pages 79–98. Springer International Publishing, 2019. doi:10.1007/978-3-030-04161-8_7.
M. J. Shon. Trapping and manipulating single molecules of DNA. PhD thesis, Harvard University, 2014. http://nrs.harvard.edu/urn-3:HUL.InstRepos:11744428.
M. J. Shon and A. E. Cohen. Mass action at the single-molecule level. J. Am. Chem. Soc., 134(35):14618–14623, 2012. doi:10.1021/ja3062425.
C. Timm. Random transition-rate matrices for the master equation. Phys. Rev. E, 80(2):021140, 2009. doi:10.1103/PhysRevE.80.021140.
L. N. Trefethen and M. Embree. Spectra and pseudospectra: The behavior of nonnormal matrices and operators. Princeton University Press, 2005. https://press.princeton.edu/books/hardcover/9780691119465/spectra-and-pseudospectra
Stochastic modeling of naïve T cell homeostasis for competing clonotypes VIA the master equation
No full textStochastic models for competing clonotypes of T cells by multivariate, continuoustime, discrete state, Markov processes have recently been proposed in the literature. A stochastic modeling framework is important because of rare events associated with small populations of some critical cell types. Usually, computational methods for these problems employ a trajectory-based approach, based on Monte Carlo simulation. This is partly because the complementary, probabilitydensity function (PDF) approaches can be expensive, but here we describe some efficient PDF approaches by directly solving the governing equations, known as the Master Equation. These computations are made very efficient through an approximation of the state space by projections and through the use of Krylov subspace methods when evolving the matrix exponential. These computational methods allow us to explore the evolution of the PDFs associated with these stochastic models, and bimodal distributions arise. Both experimental and theoretical investigations have emphasized the need to take into account effects due to aging. Thus time-dependent propensities naturally arise in immunological processes. Incorporating time-dependent propensities into the framework of the Master Equation significantly complicates the corresponding computational methods, but here we describe an efficient approach via Magnus formulas. Although this contribution focuses on the example of competing clonotypes, the general principles are relevant to multivariate Markov processes and provide fundamental techniques for computational immunology. © 2010 Society for Industrial and Applied Mathematics
Cauchy integrals for computational solutions of master equations
No full textCauchy contour integrals are demonstrated to be effective in computationally solving master equations. A fractional generalization of a bimolecular master equation is one interesting application.
References A. Andreychenko, L. Mikeev, D. Spieler, and V. Wolf. Approximate maximum likelihood estimation for stochastic chemical kinetics. EURASIP J. Bioinf. Sys. Biol., 2012:9, 2012. doi:10.1186/1687-4153-2012-9 C. N. Angstmann, I. C. Donnelly, B. I. Henry, and J. A. Nichols. A discrete time random walk model for anomalous diffusion. J. Comput. Phys., 293:53–69, 2014. doi:10.1016/j.jcp.2014.08.003 Y. Berkowitz, Y. Edery, H. Scher, and B. Berkowitz. Fickian and non-Fickian diffusion with bimolecular reactions. Phys. Rev. E, 87:032812, 2013. doi:10.1103/PhysRevE.87.032812 J. C. Butcher. On the numerical inversion of Laplace and Mellin transforms. Conference on Data Processing and Automatic Computing Machines, 117:1–8, 1957. D. Ding, D. A. Benson, A. Paster, and D. Bolster. Modeling bimolecular reactions and transport in porous media via particle tracking. Adv. Water Resour., 53:56–65, 2013. doi:10.1016/j.advwatres.2012.11.001 B. Drawert, S. Engblom, and A. Hellander. URDME: a modular framework for stochastic simulation of reaction-transport processes in complex geometries. BMC Syst. Biol., 6:76, 2012. doi:10.1186/1752-0509-6-76 T. A Driscoll, N. Hale, and L. N. Trefethen. Chebfun Guide. Pafnuty Publications, 2014. http://www.chebfun.org/docs/guide/ N. Dunford and J. Schwartz. Linear Operators I, II, III. Wiley New York, 1971. http://au.wiley.com/WileyCDA/WileyTitle/productCd-0471608483.html, http://au.wiley.com/WileyCDA/WileyTitle/productCd-0471608475.html, http://au.wiley.com/WileyCDA/WileyTitle/productCd-0471608467.html D. Fulger, E. Scalas, and G. Germano. Monte Carlo simulation of uncoupled continuous-time random walks yielding a stochastic solution of the space-time fractional diffusion equation. Phys. Rev. E, 77:021122, 2008. doi:10.1103/PhysRevE.77.021122 D. Gillespie. Markov Processes: An Introduction for Physical Scientists. Academic Press, 1991. http://www.elsevier.com/books/markov-processes/gillespie/978-0-12-283955-9 M. Hegland, C. Burden, L. Santoso, S. MacNamara, and H. Booth. A solver for the stochastic master equation applied to gene regulatory networks. J. Comput. Appl. Math., 205(2):708–724, 2006. doi:10.1016/j.cam.2006.02.053 B. I. Henry, T. A. M. Langlands, and S. L. Wearne. Anomalous diffusion with linear reaction dynamics: From continuous time random walks to fractional reaction-diffusion equations. Phys. Rev. E, 74(3):031116, 2006. doi:10.1103/PhysRevE.74.031116 N. J. Higham. Functions of Matrices. SIAM, 2008. doi:10.1137/1.9780898717778 R. Hilfer and L. Anton. Fractional master equations and fractal time random walks. Phys. Rev. E, 51:R848, 1995. doi:10.1103/PhysRevE.51.R848 K. J. in 't Hout and J. A. C. Weideman. A contour integral method for the Black–Scholes and Heston equations. SIAM J. Sci. Comput., 33:763–785, 2011. doi:10.1137/090776081 T. Jahnke and D. Altintan. Efficient simulation of discrete stochastic reaction systems with a splitting method. BIT, 50:797–822, 2010. doi:doi:10.1007/s10543-010-0286-0 T. Kato. Perturbation theory for linear operators. Springer-Verlag, 1976. http://link.springer.com/book/10.1007%2F978-3-642-66282-9 V. M. Kenkre, E. W. Montroll, and M. F. Shlesinger. Generalized master equations for continuous-time random walks. J. Stat. Phys., 9(1):45, 1973. doi:10.1007/BF01016796 M. Lopez-Fernandez and C. Palencia. On the numerical inversion of the Laplace transform in certain holomorphic mappings. Appl. Numer. Math., 51:289–303, 2004. doi:10.1016/j.apnum.2004.06.015 S. MacNamara, K. Burrage, and R. B. Sidje. Multiscale modeling of chemical kinetics via the master equation. SIAM Multiscale Model. Simul., 6(4):1146–1168, 2008. doi:10.1137/060678154 M. Magdziarz, A. Weron, and K. Weron. Fractional Fokker–Planck dynamics: Stochastic representation and computer simulation. Phys. Rev. E, 75:016708, 2007. doi:10.1103/PhysRevE.75.016708 F. Mainardi, R. Gorenflo, and A. Vivoli. Beyond the Poisson renewal process: A tutorial survey. J. Comput. Appl. Math., 2007. doi:10.1016/j.cam.2006.04.060 W. McLean. Regularity of solutions to a time-fractional diffusion equation. ANZIAM J., 52(2):123–138, 2010. doi:10.1017/S1446181111000617 W. McLean and V. Thomee. Time discretization of an evolution equation via Laplace transforms. IMA J. Numer. Anal., 24:439–463, 2004. doi:10.1093/imanum/24.3.439 R. Metzler and J. Klafter. The random walk's guide to anomalous diffusion: a fractional dynamics approach. Phys. Rep., 339:1–77, 2000. doi:10.1016/S0370-1573(00)00070-3 C. Moler and C. Van Loan. Nineteen Dubious Ways to Compute the Exponential of a Matrix, 25 Years Later. SIAM Rev., 45(1):3–49, 2003. doi:10.1137/S00361445024180 E. W. Montroll and G. H. Weiss. Random Walks on Lattices. II. J. Math. Phys., 6(2):167–181, 1965. doi:10.1063/1.1704269 I. Moret and P. Novati. On the Convergence of Krylov Subspace Methods for Matrix Mittag–Leffler Functions. SIAM J. Numer. Anal., 49(5):2144–2164, 2011. doi:10.1137/080738374 I. Podlubny. Fractional Differential Equations. Academic Press, San Diego, 1999. http://www.elsevier.com/books/fractional-differential-equations/podlubny/978-0-12-558840-9 M. Raberto, F. Rapallo, and E. Scalas. Semi-Markov Graph Dynamics. PLoS ONE, 6(8):e23370, 2011. doi:10.1371/journal.pone.0023370 S. C. Reddy and L. N. Trefethen. Pseudospectra of the convection-diffusion operator. SIAM J. Appl. Math., 54(6):1634–1649, 1994. doi:10.1137/S0036139993246982 E. B. Saff and A. D. Snider. Fundamentals of complex analysis with applications to engineering and science. Pearson Education, 2003. http://www.pearsonhighered.com/educator/product/Fundamentals-of-Complex-Analysis-with-Applications-to-Engineering-Science-and-Mathematics/9780139078743.page E. Scalas, R. Gorenflo, and F. Mainardi. Uncoupled continuous-time random walks: Solution and limiting behavior of the master equation. Phys. Rev. E, 69:011107, 2004. doi:10.1103/PhysRevE.69.011107 D. Sheen, I. H. Sloan, and V. Thomee. A parallel method for time discretization of parabolic equations based on Laplace transformation and quadrature. IMA J. Numer. Anal., 23:269–299, 2003. doi:10.1093/imanum/23.2.269 M. J. Shon and A. E. Cohen. Mass action at the single-molecule level. J. Am. Chem. Soc., 134(35):14618–14623, 2012. doi:10.1021/ja3062425 G. Strang and S. MacNamara. Functions of difference matrices are Toeplitz plus Hankel. SIAM Rev., 56(3):525–546, 2014. doi:10.1137/120897572 A. Talbot. The accurate numerical inversion of Laplace transforms. J. Inst. Math. Appl., 23:97–120, 1979. doi:10.1093/imamat/23.1.97 L. N. Trefethen. Approximation Theory and Approximation Practice. SIAM, Philadelphia, 2013. http://bookstore.siam.org/ot128/ L. N. Trefethen and M. Embree. Spectra and pseudospectra: the behavior of nonnormal matrices and operators. Princeton University Press, 2005. http://press.princeton.edu/titles/8113.html L. N. Trefethen and J. A. C. Weideman. The exponentially convergent trapezoidal rule. SIAM Rev., 56(3):385–458, 2014. doi:10.1137/130932132 N. G. van Kampen. Stochastic Processes in Physics and Chemistry. Elsevier Science, 2001. http://www.elsevier.com/books/stochastic-processes-in-physics-and-chemistry/van-kampen/978-0-444-52965-7 J. A. C. Weideman. Improved contour integral methods for parabolic PDEs. IMA J. Numer. Anal., 30:334–350, 2010. doi:10.1093/imanum/drn074 J. A. C. Weideman and L. N. Trefethen. Parabolic and hyperbolic contours for computing the bromwich integral. Math. Comput., 76:1341–1356, 2007. doi:10.1090/S0025-5718-07-01945-X T. G. Wright. Eigtool, 2002. http://www.comlab.ox.ac.uk/pseudospectra/eigtool/. Q. Yang, T. Moroney, K. Burrage, I. Turner, and F. Liu. Novel numerical methods for time-space fractional reaction diffusion equations in two dimensions. ANZIAM J., 52:395–409, 2011. http://journal.austms.org.au/ojs/index.php/ANZIAMJ/article/view/3791/146
Multiscale modeling of chemical kinetics via the master equation
No full textWe present numerical methods for both the direct solution and simulation of the chemical master equation (CME), and, compared to popular methods in current use, such as the Gillespie stochastic simulation algorithm (SSA) and τ-Leap approximations, this new approach has the advantage of being able to detect when the system has settled down to equilibrium. This improved performance is due to the incorporation of information from the associated CME, a valuable complementary approach to the SSA that has often been felt to be too computationally inefficient. Hybrid methods, that combine these complementary approaches and so are able to detect equilibrium while maintaining the efficiency of the leap methods, are also presented. Amongst CME-solvers the recently suggested finite state projection algorithm is especially well suited to this purpose and has been adapted here for the task, leading to a type of “exact τ-Leap.” It is also observed that a CMEsolver is often more efficient than an SSA or even a τ-Leap approach for computing moments of the solution such as the mean and variance. These techniques are demonstrated on a test suite of five biologically inspired models, namely, stochastic models of the genetic toggle, receptor oligomerization, the Schl¨ogl reactions, Goutsias’ model of regulated gene transcription, and a decaying-dimerizing reaction set. For the gene toggle it is observed that important experimentally measurable traits such as the percentage of cells that undergo so-called switching may also be more efficiently approximated via a CME-based approach
Building on MacNamara v. Korean Air Lines
No full textThis Note explores the possibility of applying Title VII\u27s disparate impact liability theory against foreign companies operating under Treaties of Friendship, Commerce, and Navigation (FCN Treaties). The author questions the reasoning of MacNamara v. Korean Air Lines, which applied disparate treatment, but not disparate impact, against a Korean company operating under an FCN Treaty. According to MacNamara, if courts permit plaintiffs in Title VII-FCN Treaty cases to utilize the disparate impact theory and cite statistical disparities in the racial composition of the work force as evidence of discrimination, employers could be held liable merely for exercising their FCN Treaty rights. This Note concludes that the MacNamara court ignored the complexity and costliness of presenting statistical data. More importantly, recovery under the disparate impact theory has become extremely difficult as a result of the Supreme Court\u27s subsequent decision Wards Cove Packing v. Atonio. Furthermore, the author concludes that any increase in Title VII liability--because of either narrowed FCN Treaty rights or the application of disparate impact analysis--likely will not affect foreign investment in the United States. Fear of widespread divestment in the United States should not be the controlling factor in the resolution of tension between Title VII and FCN Treaties. The author advocates that victims of employment discrimination should be entitled to bring disparate impact, as well as disparate treatment, claims in cases involving foreign corporations operating under FCN Treaties
An improved dynamic Finite State Projection algorithm for the numerical solution of the chemical master equation with applications
No full textRecently, Munsky and Khammash suggested the Finite State Projection (FSP) algorithm for the numerical solution of the Chemical Master Equation, which provides a discrete and stochastic modelling framework for chemical kinetics. The important question of whether or not the algorithm is guaranteed to terminate is not addressed in the original work. We show that the well-known explosive birth process provides a counter example. We also give sufficient criteria for a model to be suitable for the FSP technique. We demonstrate the FSP technique on three novel applications. Results are presented for: (i) the Schlogl reactions; (ii) another example from Gillespie's celebrated book; and (iii) models for the role that dimerization plays in reducing noise in simple gene regulatory networks. Finally, we augment the dimerization model to include tetramers and show that this enhances the noise reduction properties of the network
Inexact uniformization method for computing transient distributions of Markov chains
No full textThe uniformization method (also known as randomization) is a numerically stable algorithm for computing transient distributions of a continuous time Markov chain. When the solution is needed after a long run or when the convergence is slow, the uniformization method involves a large number of matrix-vector products. Despite this, the method remains very popular due to its ease of implementation and its reliability in many practical circumstances. Because calculating the matrix-vector product is the most time-consuming part of the method, overall efficiency in solving large-scale problems can be significantly enhanced if the matrix-vector product is made more economical. In this paper, we incorporate a new relaxation strategy into the uniformization method to compute the matrix-vector products only approximately. We analyze the error introduced by these inexact matrix-vector products and discuss strategies for re. ning the accuracy of the relaxation while reducing the execution cost. Numerical experiments drawn from computer systems and biological systems are given to show that significant computational savings are achieved in practical applications
- …
