Gillespie algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In probability theory and computational science, the Gillespie algorithm, also known as the stochastic simulation algorithm (SSA), is a method for generating statistically exact sample trajectories of certain continuous-time Markov jump processes. It is especially associated with the simulation of coupled chemical reaction systems. Daniel Gillespie presented the method in 1976 and developed it further in 1977. The method is widely used in computational systems biology, particularly when the numbers of reacting molecules are small enough that stochastic fluctuations are important. Gillespie-type algorithms are also used in network epidemiology to simulate stochastic epidemic spreading on complex networks, including continuous-time SI, SIS, and SIR processes. Mathematically, the algorithm is a form of dynamic Monte Carlo method and is closely related to kinetic Monte Carlo methods.

In probability theory and computational science, the Gillespie algorithm, also known as the stochastic simulation algorithm (SSA), is a method for generating statistically exact sample trajectories of certain continuous-time Markov jump processes. It is especially associated with the simulation of coupled chemical reaction systems. Daniel Gillespie presented the method in 1976 and developed it further in 1977. The method is widely used in computational systems biology, particularly when the numbers of reacting molecules are small enough that stochastic fluctuations are important. Gillespie-type algorithms are also used in network epidemiology to simulate stochastic epidemic spreading on complex networks, including continuous-time SI, SIS, and SIR processes. Mathematically, the algorithm is a form of dynamic Monte Carlo method and is closely related to kinetic Monte Carlo methods. a_0(\boldsymbol{x})=\sum_j a_j(\boldsymbol{x}). Provided that the process is Markovian, the waiting time \tau until the next event is exponentially distributed with rate a_0(\boldsymbol{x}) . The joint probability density that the next event occurs after a waiting time \tau and is reaction j is p(\tau,j\mid\boldsymbol{x},t)=a_j(\boldsymbol{x})\exp[-a_0(\boldsymbol{x})\tau]. Thus, the simulation requires two random choices: the time of the next event and which event occurs. Using two independent pseudorandom numbers r_1 and r_2 , uniformly distributed on (0,1) , the waiting time can be generated as \tau=\frac{1}{a_0(\boldsymbol{x})}\ln\left(\frac{1}{r_1}\right). The next reaction j is the smallest integer satisfying \sum_{j'=1}^{j} a_{j'}(\boldsymbol{x}) > r_2 a_0(\boldsymbol{x}). Initialize the time t=t_0 and state \boldsymbol{x}=\boldsymbol{x}_0 . Evaluate each propensity a_j(\boldsymbol{x}) and their total a_0(\boldsymbol{x}) . Generate the waiting time \tau and select the next reaction j . Advance the time according to t\leftarrow t+\tau . Update the state according to \boldsymbol{x}\leftarrow\boldsymbol{x}+\boldsymbol{\nu}_j , where \boldsymbol{\nu}_j is the state-change vector associated with reaction j . Record the state if required and repeat until the chosen stopping condition is reached. Each realization produced in this way is a sample trajectory of the corresponding stochastic process. A + B AB There are two possible reactions. An molecule and a molecule can combine to produce an dimer, or an existing dimer can dissociate. Let the rate constant for dimer formation be k_\mathrm{D} and the rate constant for dissociation be k_\mathrm{B} . If the system contains n_\mathrm{A} molecules of , n_\mathrm{B} molecules of , and n_\mathrm{AB} dimers, the two propensities are a_1=k_\mathrm{D}n_\mathrm{A}n_\mathrm{B} and a_2=k_\mathrm{B}n_\mathrm{AB}. The total reaction propensity is therefore a_0=k_\mathrm{D}n_\mathrm{A}n_\mathrm{B}+k_\mathrm{B}n_\mathrm{AB}. The waiting time until the next reaction is sampled from an exponential distribution with mean 1/a_0 . Once the waiting time has been generated, the probability that the next event is dimer formation is P(\mathrm{A+B\rightarrow AB})=\frac{k_\mathrm{D}n_\mathrm{A}n_\mathrm{B}}{a_0}, while the probability of dissociation is P(\mathrm{AB\rightarrow A+B})=\frac{k_\mathrm{B}n_\mathrm{AB}}{a_0}. If dimer formation occurs, n_\mathrm{A} and n_\mathrm{B} each decrease by one and n_\mathrm{AB} increases by one. If dissociation occurs, the opposite update is made. Repeatedly sampling the waiting time and reaction type generates one stochastic trajectory of the system.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373866241 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.