Path ensembles and path sampling in nonequilibrium stochastic systems

Markovian models based on the stochastic master equation are often encountered in single molecule dynamics, reaction networks, and nonequilibrium problems in chemistry, physics, and biology. An efficient and convenient method to simulate these systems is the kinetic Monte Carlo algorithm which generates continuous-time stochastic trajectories. We discuss an alternative simulation method based on sampling of stochastic paths. Utilizing known probabilities of stochastic paths, it is possible to apply Metropolis Monte Carlo in path space to generate a desired ensemble of stochastic paths. The method is a generalization of the path sampling idea to stochastic dynamics, and is especially suited for the analysis of rare paths which are not often produced in the standard kinetic Monte Carlo procedure. Two generic examples are presented to illustrate the methodology.     

Accurate hybrid stochastic simulation of a system of coupled chemical or biochemical reactions

The dynamical solution of a well-mixed, nonlinear stochastic chemical kinetic system, described by the Master equation, may be exactly computed using the stochastic simulation algorithm. However, because the computational cost scales with the number of reaction occurrences, systems with one or more "fast" reactions become costly to simulate. This paper describes a hybrid stochastic method that partitions the system into subsets of fast and slow reactions, approximates the fast reactions as a continuous Markov process, using a chemical Langevin equation, and accurately describes the slow dynamics using the integral form of the "Next Reaction" variant of the stochastic simulation algorithm. The key innovation of this method is its mechanism of efficiently monitoring the occurrences of slow, discrete events while simultaneously simulating the dynamics of a continuous, stochastic or deterministic process. In addition, by introducing an approximation in which multiple slow reactions may occur within a time step of the numerical integration of the chemical Langevin equation, the hybrid stochastic method performs much faster with only a marginal decrease in accuracy. Multiple examples, including a biological pulse generator and a large-scale system benchmark, are simulated using the exact and proposed hybrid methods as well as, for comparison, a previous hybrid stochastic method. Probability distributions of the solutions are compared and the weak errors of the first two moments are computed. In general, these hybrid methods may be applied to the simulation of the dynamics of a system described by stochastic differential, ordinary differential, and Master equations.     

Reduction and solution of the chemical master equation using time scale separation and finite state projection

The dynamics of chemical reaction networks often takes place on widely differing time scales--from the order of nanoseconds to the order of several days. This is particularly true for gene regulatory networks, which are modeled by chemical kinetics. Multiple time scales in mathematical models often lead to serious computational difficulties, such as numerical stiffness in the case of differential equations or excessively redundant Monte Carlo simulations in the case of stochastic processes. We present a model reduction method for study of stochastic chemical kinetic systems that takes advantage of multiple time scales. The method applies to finite projections of the chemical master equation and allows for effective time scale separation of the system dynamics. We implement this method in a novel numerical algorithm that exploits the time scale separation to achieve model order reductions while enabling error checking and control. We illustrate the efficiency of our method in several examples motivated by recent developments in gene regulatory networks.     

A variational approach to the stochastic aspects of cellular signal transduction

Cellular signaling networks have evolved to cope with intrinsic fluctuations, coming from the small numbers of constituents, and the environmental noise. Stochastic chemical kinetics equations govern the way biochemical networks process noisy signals. The essential difficulty associated with the master equation approach to solving the stochastic chemical kinetics problem is the enormous number of ordinary differential equations involved. In this work, we show how to achieve tremendous reduction in the dimensionality of specific reaction cascade dynamics by solving variationally an equivalent quantum field theoretic formulation of stochastic chemical kinetics. The present formulation avoids cumbersome commutator computations in the derivation of evolution equations, making the physical significance of the variational method more transparent. We propose novel time-dependent basis functions which work well over a wide range of rate parameters. We apply the new basis functions to describe stochastic signaling in several enzymatic cascades and compare the results so obtained with those from alternative solution techniques. The variational Ansatz gives probability distributions that agree well with the exact ones, even when fluctuations are large and discreteness and nonlinearity are important. A numerical implementation of our technique is many orders of magnitude more efficient computationally compared with the traditional Monte Carlo simulation algorithms or the Langevin simulations.     

A data-integrated method for analyzing stochastic biochemical networks

Variability and fluctuations among genetically identical cells under uniform experimental conditions stem from the stochastic nature of biochemical reactions. Understanding network function for endogenous biological systems or designing robust synthetic genetic circuits requires accounting for and analyzing this variability. Stochasticity in biological networks is usually represented using a continuous-time discrete-state Markov formalism, where the chemical master equation (CME) and its kinetic Monte Carlo equivalent, the stochastic simulation algorithm (SSA), are used. These two representations are computationally intractable for many realistic biological problems. Fitting parameters in the context of these stochastic models is particularly challenging and has not been accomplished for any but very simple systems. In this work, we propose that moment equations derived from the CME, when treated appropriately in terms of higher order moment contributions, represent a computationally efficient framework for estimating the kinetic rate constants of stochastic network models and subsequent analysis of their dynamics. To do so, we present a practical data-derived moment closure method for these equations. In contrast to previous work, this method does not rely on any assumptions about the shape of the stochastic distributions or a functional relationship among their moments. We use this method to analyze a stochastic model of a biological oscillator and demonstrate its accuracy through excellent agreement with CME/SSA calculations. By coupling this moment-closure method with a parameter search procedure, we further demonstrate how a model's kinetic parameters can be iteratively determined in order to fit measured distribution data.     

The finite state projection algorithm for the solution of the chemical master equation

This article introduces the finite state projection (FSP) method for use in the stochastic analysis of chemically reacting systems. One can describe the chemical populations of such systems with probability density vectors that evolve according to a set of linear ordinary differential equations known as the chemical master equation (CME). Unlike Monte Carlo methods such as the stochastic simulation algorithm (SSA) or tau leaping, the FSP directly solves or approximates the solution of the CME. If the CME describes a system that has a finite number of distinct population vectors, the FSP method provides an exact analytical solution. When an infinite or extremely large number of population variations is possible, the state space can be truncated, and the FSP method provides a certificate of accuracy for how closely the truncated space approximation matches the true solution. The proposed FSP algorithm systematically increases the projection space in order to meet prespecified tolerance in the total probability density error. For any system in which a sufficiently accurate FSP exists, the FSP algorithm is shown to converge in a finite number of steps. The FSP is utilized to solve two examples taken from the field of systems biology, and comparisons are made between the FSP, the SSA, and tau leaping algorithms. In both examples, the FSP outperforms the SSA in terms of accuracy as well as computational efficiency. Furthermore, due to very small molecular counts in these particular examples, the FSP also performs far more effectively than tau leaping methods.     

Mechanism-based chemical understanding of chiral symmetry breaking in the Soai reaction. A combined probabilistic and deterministic description of chemical reactions

The experimentally observed distribution of enantiomers in the Soai reaction is interpreted in this Article on the basis of a chemical mechanism using a newly developed stochastic kinetic method, accelerated Monte Carlo simulation combined with deterministic continuation and symmetrization. The method is in principle suitable for handling large mechanisms with realistic particle numbers and could be useful for any case where the kinetics of a process shows inherent random fluctuations. The mechanism shows how a slow initial reaction combined with efficient and highly enantioselective autocatalysis can give rise to chiral symmetry breaking under completely nonchiral external conditions.     

An analytical approach to solutions of master equations for stochastic nonlinear reactions

In this paper we consider a class of nonlinear reactions which are important in stochastic reaction networks. We find the exact solution of the chemical master equation for a class of irreversible and reversible nonlinear reactions. We also present the explicit form of the equilibrium probability solution of the reactions. The results can be used for analyzing stochastic dynamics of important reactions such as binding/unbinding reaction and protein dimerization.     

A constrained approach to multiscale stochastic simulation of chemically reacting systems

Stochastic simulation of coupled chemical reactions is often computationally intensive, especially if a chemical system contains reactions occurring on different time scales. In this paper, we introduce a multiscale methodology suitable to address this problem, assuming that the evolution of the slow species in the system is well approximated by a Langevin process. It is based on the conditional stochastic simulation algorithm (CSSA) which samples from the conditional distribution of the suitably defined fast variables, given values for the slow variables. In the constrained multiscale algorithm (CMA) a single realization of the CSSA is then used for each value of the slow variable to approximate the effective drift and diffusion terms, in a similar manner to the constrained mean-force computations in other applications such as molecular dynamics. We then show how using the ensuing Fokker-Planck equation approximation, we can in turn approximate average switching times in stochastic chemical systems.     

Multiple‐Well,multiple‐path unimolecular reaction systems. I. MultiWell computer program suite

Unimolecular reaction systems in which multiple isomers undergo simultaneous reactions via multiple decomposition reactions and multiple isomerization reactions are of fundamental interest in chemical kinetics. The computer program suite described here can be used to treat such coupled systems, including the effects of collisional energy transfer (weak collisions). The program suite consists of MultiWell, which solves the internal energy master equation for complex unimolecular reactions systems; DenSum, which calculates sums and densities of states by an exact‐count method; MomInert, which calculates external principal moments of inertia and internal rotation reduced moments of inertia; and Thermo, which calculates equilibrium constants and other thermodynamics quantities. MultiWell utilizes a hybrid master equation approach, which performs like an energy‐grained master equation at low energies and a continuum master equation in the vibrational quasicontinuum. An adaptation of Gillespie's exact stochastic method is used for the solution. The codes are designed for ease of use. Details are presented of various methods for treating weak collisions with virtually any desired collision step‐size distribution and for utilizing RRKM theory for specific unimolecular rate constants. © 2001 John Wiley & Sons, Inc. Int J Chem Kinet 33: 232–245, 2001     

自由基聚合反应的Monte Carlo模拟方法

本文将化学反应动力学的MonteCarlo模拟方法运用到引发剂引发的自由基聚合反应的非稳态动力学,针对自由基聚合反应动力学数值模拟所特有的"无伸缩问题",采用"偏倚抽样法"解决了MonteCarlo模拟中的"无伸缩问题",模拟结果与非稳态动力学解的结果完全一致,此算法易推广到研究更复杂的自由基聚合反应体系。     

Stochastic simulation of catalytic surface reactions in the fast diffusion limit

The master equation of a lattice gas reaction tracks the probability of visiting all spatial configurations. The large number of unique spatial configurations on a lattice renders master equation simulations infeasible for even small lattices. In this work, a reduced master equation is derived for the probability distribution of the coverages in the infinite diffusion limit. This derivation justifies the widely used assumption that the adlayer is in equilibrium for the current coverages and temperature when all reactants are highly mobile. Given the reduced master equation, two novel and efficient simulation methods of lattice gas reactions in the infinite diffusion limit are derived. The first method involves solving the reduced master equation directly for small lattices, which is intractable in configuration space. The second method involves reducing the master equation further in the large lattice limit to a set of differential equations that tracks only the species coverages. Solution of the reduced master equation and differential equations requires information that can be obtained through short, diffusion-only kinetic Monte Carlo simulation runs at each coverage. These simulations need to be run only once because the data can be stored and used for simulations with any set of kinetic parameters, gas-phase concentrations, and initial conditions. An idealized CO oxidation reaction mechanism with strong lateral interactions is used as an example system for demonstrating the reduced master equation and deterministic simulation techniques.     

Steady-state fluctuations of a genetic feedback loop: an exact solution

Genetic feedback loops in cells break detailed balance and involve bimolecular reactions; hence, exact solutions revealing the nature of the stochastic fluctuations in these loops are lacking. We here consider the master equation for a gene regulatory feedback loop: a gene produces protein which then binds to the promoter of the same gene and regulates its expression. The protein degrades in its free and bound forms. This network breaks detailed balance and involves a single bimolecular reaction step. We provide an exact solution of the steady-state master equation for arbitrary values of the parameters, and present simplified solutions for a number of special cases. The full parametric dependence of the analytical non-equilibrium steady-state probability distribution is verified by direct numerical solution of the master equations. For the case where the degradation rate of bound and free protein is the same, our solution is at variance with a previous claim of an exact solution [J. E. M. Hornos, D. Schultz, G. C. P. Innocentini, J. Wang, A. M. Walczak, J. N. Onuchic, and P. G. Wolynes, Phys. Rev. E 72, 051907 (2005), and subsequent studies]. We show explicitly that this is due to an unphysical formulation of the underlying master equation in those studies.     

Rate kernel theory for pseudo-first-order kinetics of diffusion-influenced reactions and application to fluorescence quenching kinetics

Theoretical foundation of rate kernel equation approaches for diffusion-influenced chemical reactions is presented and applied to explain the kinetics of fluorescence quenching reactions. A many-body master equation is constructed by introducing stochastic terms, which characterize the rates of chemical reactions, into the many-body Smoluchowski equation. A Langevin-type of memory equation for the density fields of reactants evolving under the influence of time-independent perturbation is derived. This equation should be useful in predicting the time evolution of reactant concentrations approaching the steady state attained by the perturbation as well as the steady-state concentrations. The dynamics of fluctuation occurring in equilibrium state can be predicted by the memory equation by turning the perturbation off and consequently may be useful in obtaining the linear response to a time-dependent perturbation. It is found that unimolecular decay processes including the time-independent perturbation can be incorporated into bimolecular reaction kinetics as a Laplace transform variable. As a result, a theory for bimolecular reactions along with the unimolecular process turned off is sufficient to predict overall reaction kinetics including the effects of unimolecular reactions and perturbation. As the present formulation is applied to steady-state kinetics of fluorescence quenching reactions, the exact relation between fluorophore concentrations and the intensity of excitation light is derived.     

Transition path sampling for discrete master equations with absorbing states

Transition path sampling (TPS) algorithms have been implemented with deterministic dynamics, with thermostatted dynamics, with Brownian dynamics, and with simple spin flip dynamics. Missing from the TPS repertoire is an implementation with kinetic Monte Carlo (kMC), i.e., with the underlying dynamics coming from a discrete master equation. We present a new hybrid kMC-TPS algorithm and prove that it satisfies detailed balance in the transition path ensemble. The new algorithm is illustrated for a simplified Markov State Model of trp-cage folding. The transition path ensemble from kMC-TPS is consistent with that obtained from brute force kMC simulations. The committor probabilities and local fluxes for the simple model are consistent with those obtained from exact methods for simple master equations. The new kMC-TPS method should be useful for analysis of rare transitions in complex master equations where the individual states cannot be enumerated and therefore where exact solutions cannot be obtained.     

Overcoming stiffness in stochastic simulation stemming from partial equilibrium: a multiscale Monte Carlo algorithm

In this paper the problem of stiffness in stochastic simulation of singularly perturbed systems is discussed. Such stiffness arises often from partial equilibrium or quasi-steady-state type of conditions. A multiscale Monte Carlo method is discussed that first assesses whether partial equilibrium is established using a simple criterion. The exact stochastic simulation algorithm (SSA) is next employed to sample among fast reactions over short time intervals (microscopic time steps) in order to compute numerically the proper probability distribution function for sampling the slow reactions. Subsequently, the SSA is used to sample among slow reactions and advance the time by large (macroscopic) time steps. Numerical examples indicate that not only long times can be simulated but also fluctuations are properly captured and substantial computational savings result.     

Kinetics of autocatalysis in small systems

Autocatalysis is a ubiquitous chemical process that drives a plethora of biological phenomena, including the self-propagation of prions etiological to the Creutzfeldt-Jakob disease and bovine spongiform encephalopathy. To explain the dynamics of these systems, we have solved the chemical master equation for the irreversible autocatalytic reaction A+B-->2A. This solution comprises the first closed form expression describing the probabilistic time evolution of the populations of autocatalytic and noncatalytic molecules from an arbitrary initial state. Grand probability distributions are likewise presented for autocatalysis in the equilibrium limit (A+B <==>2A), allowing for the first mechanistic comparison of this process with chemical isomerization (B<==>A) in small systems. Although the average population of autocatalytic (i.e., prion) molecules largely conforms to the predictions of the classical "rate law" approach in time and the law of mass action at equilibrium, thermodynamic differences between the entropies of isomerization and autocatalysis are revealed, suggesting a "mechanism dependence" of state variables for chemical reaction processes. These results demonstrate the importance of chemical mechanism and molecularity in the development of stochastic processes for chemical systems and the relationship between the stochastic approach to chemical kinetics and nonequilibrium thermodynamics.     

O—酰基—α—酮肟光分解反应的Monte Carlo处理

本文首次对光化学反应体系用Monte Carlo方法进行模拟处理。通过5个O-酰基-α-酮肟光分解反应的Monte Carlo模拟,可避免解析解中由于对吸收光强须采用一级近似求解动力学微分方程组,而造成拟合反应在后期产生与实验结果的偏差。     

A comparative study of the master equation approach and the discrete galerkin method for the simulation of free radical polymerization

The present article deals with the mathematical treatment of free radical polymerization reactions. As a typical example the synthesis of poly(methyl methacrylate) under realistic experimental conditions is investigated. Since the mathematical treatment of the kinetic rate equations raises severe numerical problems, alternative approaches are required. In this paper two of these methods, i.e. the discrete Galerkin method and the master equation approach, are compared. The discrete Galerkin method circumvents difficulties encountered by the direct integration of the kinetic rate equations but requires much a priori knowledge of the chemical reaction system. Within the framework of the master equation approach the polymerization reaction is regarded as a stochastic process. For the simulation of this stochastic process a modified algorithm is presented. The example of the polymerization of methyl methacrylate shows that the master equation approach is an efficient tool in the simulation of free radical polymerization reactions.