Skip to main content

numerical integration - Gillespie Stochastic Simulation Algorithm


The Gillespie SSA is a Monte Carlo stochastic simulation algorithm to find the trajectory of a dynamic system described by a reaction (or interaction) network, e.g. chemical reactions or ecological problems. It was introduced by Dan Gillespie in 1977 (see paper here). It is used in case of small molecular numbers (or species abundance) where numerical integration of the related differential equation system is not appropriate due to hard stochastic effects (i.e. the death of a single individual might make a large impact on the population).


Can you do it with Mathematica? Is it general enough? Is it fast?



Answer



Yes you can. Below is a fairly general, Mathematica-compiled, fast and robust version.


Examples


1. Michaelis-Menten kinetics



Michaelis-Menten kinetics for enzyme-directed substrate conversion. The enzyme (e) converts the susbtrate (s) through an enzyme-substrate complex (c) to the product (p). For comparison, I've included the deterministic ODE system solved by NDSolve.


ClearAll[e, s, c, p, t];
reactions = {e + s -> c, c -> e + s, c -> e + p};
vars = {e, s, c, p};
rates = {1.1, .1, .8};
init = <|e -> 100, s -> 100, c -> 0, p -> 0|>;

det = NDSolveValue[{
e'[t] == .9 c[t] - 1.1 e[t] s[t],
s'[t] == .1 c[t] - 1.1 e[t] s[t],

c'[t] == 1.1 e[t] s[t] - .9 c[t],
p'[t] == .8 c[t],
e[0] == 100, s[0] == 100, c[0] == 0, p[0] == 0}, vars, {t, 0, 10}];
sto = GillespieSSA[reactions, init, rates, {0, 10}];
op = {PlotStyle -> Thick, PlotTheme -> "Scientific"};
Row@{Plot[Evaluate@Through@det@t, {t, 0, 10}, Evaluate@op,
PlotLabel -> "deterministic ODE"], Spacer@10,
Plot[Evaluate@Through@sto@t, {t, 0, 10}, Evaluate@op,
PlotLabel -> "stochastic SSA"]}


Mathematica graphics


2. Lotka-Volterra predator-prey dynamics


Lotka-Volterra dynamics. I omit the conversion to continuous differential equations from now on, leaving it to the "educated reader". x -> Null indicates that the species is removed without producing waste material (at least one that is tracked). Similarly, Null -> x indicates a zero-order reaction where x is generated spontaneously (or is entering from the external environment).


ClearAll[y, x];
reactions = {y -> 2 y, y + x -> 2 x, x -> Null};
vars = {y, x};
rates = {1, .005, .6};
init = <|y -> 50, x -> 100|>;

sto = GillespieSSA[reactions, init, rates, {0, 100}]


Mathematica graphics


3. Circadian cycle


ClearAll[a, p, i];
reactions = {a -> 2 a, a -> a + p, p -> i, a + i -> i, i -> Null};
vars = {a, p, i};
init = <|a -> 100, p -> 100, i -> 100|>;
rates = {1, .08, .6, .01, .4};

sto = GillespieSSA[reactions, init, rates, {0, 400}];


Mathematica graphics


4. Oregonator


The Oregonator is a model of the Belousov-Zhabotinsky reactions. Here I used the resolution argument to speed up evaluation (only every 100th step is stored).


ClearAll[a, b, c];
reactions = {b -> a, a + b -> Null, a -> 2 a + c, 2 a -> Null, c -> b};
vars = {a, b, c};
init = <|a -> 1, b -> 2, c -> 3|>
rates = {2, .1, 104, .016, 26};


sto = GillespieSSA[reactions, init, rates, {0, 4, 100}];

Mathematica graphics


Usage


The function accepts the following arguments:


 GillespieSSA[
{r1, r2, ...}, (* list of elementary reaction steps as Rules *)
<|y1 -> y1[0], y2 -> y2[0], ...|>, (* variables with initial values at t==0 *)
{c1, c2, ...}, (* reaction rate constants, for each reaction *)
<|y1 -> f1, y2 -> f2, ...|>, (* linear in/outflux for each variable;

can be left out, in which case 0 will be used*)
{mint, maxt, res} (* {start time, end time, step resolution};
resolution can be omitted, defaulting to 1 *)
]

It returns an InterpolatingFunction (with InterpolationOrder -> 0) as each variable's solution function, to comply with the result produced by NDSolve. Initial values are taken to be the values at t == mint. The maximal allowed step size (10^7) is hardcoded in iterations, change it for your needs.


Note, that the Gillespie method is stochastic: it will convert continuous reaction rates into discrete-valued reaction propensities. It cannot accept reactions where stoichiometric factors are not integer numbers. Also, it gives a different realization every time it is run (if the random generator is not reseeded) due to its stochastic nature. Moreover, at small molecular/species amounts, stochastic effects could cause extinction and produce different results as in the deterministic, continuous case (NDSolve).


Code


ClearAll[GillespieSSA];
GillespieSSA[res : {__Rule}, in_Association,

rateconst_?VectorQ, influx_Association: <||>,
{mint_?NumberQ, maxt_?NumberQ, dstep_Integer: 1}] := Module[
{vars, reactant, product, balance, propensities, initialValues,
fluxRates, symRates, rep, stepList, iterations = 10^7, step,
compiled, times, rest},

(* Pre-generating a list is much faster than iteratively calling one-by-one. *)
stepList = N@RandomVariate[ExponentialDistribution@1, iterations + 1];

{vars, initialValues} = {Keys@in, Values@in};

{reactant, product} =
Outer[Coefficient[#1, #2] &, #, vars, 1] & /@
Transpose@(List @@@ res);
balance = product - reactant;
propensities =
Inner[Binomial[#2, #1] &, reactant, vars, Times]*
PadRight[rateconst, Length@res, 1];
fluxRates = If[influx === <||>, 0 & /@ vars, vars /. influx];

Block[{count},

rep = Thread[vars -> Table[Indexed[count, i], {i, Length@vars}]];
symRates = propensities /. rep;
compiled = ReleaseHold[
Hold@Compile[{
{init, _Integer, 1}, {flux, _Integer, 1}, {bal, _Integer, 2},
{dtList, _Real, 1}, {min, _Real}, {max, _Real},
{iter, _Integer}, {resol, _Integer}},
Module[{
count = init, rates, i = 1, c = 1, t = min, dt, ff, f, range,
r, fReal = 0. & /@ flux, rateSum, data = Internal`Bag[]},

rates = "SymbolicRates";
rateSum = N@Total@rates;
range = Range@Length@rates;
Internal`StuffBag[data, Internal`Bag[Join[{t}, N@count]]];

While[Total@count > 0. && rateSum > 0. && t <= max && i <= iter,
i++;
dt = dtList[[i]]/rateSum;
t = t + dt;
r = RandomChoice[rates -> range];

(* Fractional part is carried over to minimize undersampling error *)
ff = (flux*dt) + fReal;
f = IntegerPart@ff;
fReal = ff - f;
(* `count` is maintained as an integer not to loose precision. *)
count = Max[0, #] & /@ (count + bal[[r]] + f);
If[Mod[i, resol] == 0, c++;
Internal`StuffBag[data, Internal`Bag[Join[{t}, N@count]]];];
rates = "SymbolicRates";
rateSum = N@Total@rates;

];
If[t < max && i < iter, c++;
Internal`StuffBag[data, Internal`Bag[Join[{max}, N@count]]]];
Table[Internal`BagPart[Internal`BagPart[data, j], All], {j, c}]
],
Parallelization -> True , RuntimeAttributes -> Listable,
RuntimeOptions -> "Speed",
CompilationOptions -> {"InlineExternalDefinitions" -> True,
"InlineCompiledFunctions" -> True}
] /. "SymbolicRates" -> symRates];


{times, rest} = {First@#, Rest@#} &@Transpose@compiled[
Round@initialValues, N@fluxRates, Round@balance,
N@stepList, N@mint, N@maxt, Round@iterations, dstep];
Interpolation[Transpose@{times, #}, InterpolationOrder -> 0] & /@ rest
]];

Comments

Popular posts from this blog

plotting - How to draw lines between specified dots on ListPlot?

I would like to create a plot where I have unconnected dots and some connected. So far, I have figured out how to draw the dots. My code is the following: ListPlot[{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {1, 10}, {2, 11}, {3, 12}, {4,13}, {2.5, 7}}, Ticks -> {{1, 2, 3, 4}, None}, AxesStyle -> Thin, TicksStyle -> Directive[Black, Bold, 12], Mesh -> Full] I have thought using ListLinePlot command, but I don't know how to specify to the command to draw only selected lines between the dots. Do have any suggestions/hints on how to do that? Thank you. Answer One possibility would be to use Epilog with Line : ListPlot[ {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {1, 10}, {2, 11}, {3, 12}, {4, 13}, {2.5, 7}}, Ticks -> {{1, 2, 3, 4}, None}, AxesStyle -> Thin, TicksStyle -> Directive[Black, Bold, 12], Mesh -> Full, Epilog -> { Line[ ...

list manipulation - Selecting multiple columns from a matrix?

Sample data: data = { {{2013, 1, 1}, 24.13, 167.67, 231.82}, {{2013, 1, 2}, 32.15, 170.92, 225.99}, {{2013, 1, 3}, 35.43, 172.68, 221.67}, {{2013, 1, 4}, 36.73, 173.05, 218.32}, {{2013, 1, 5}, 58.19, 165.96, 197.05}, {{2013, 1, 6}, 69.99, 163.50, 187.52}, {{2013, 1, 7}, 71.37, 154.21, 175.58}, {{2013, 1, 8}, 72.51, 149.66, 163.25}}; I want a DateListPlot with three graphs, so for a matrix formed by columns 1 and 2, one for columns 1 and 3, and 1 for columns 1 and 4. At the moment I'm using this code: data2 = Transpose[{data[[All, 1]], data[[All, 2]]}]; data3 = Transpose[{data[[All, 1]], data[[All, 3]]}]; data4 = Transpose[{data[[All, 1]], data[[All, 4]]}]; DateListPlot[{data2, data3, data4}, Joined -> True, Filling -> {3 -> {1}}] but I have a hunch that this can be done more efficiently. I don't like the Transpose s in particular. Any ideas? edit (for extra credit) What if I need to multiply the second column by 2, which in my solution is simp...

calculus and analysis - Integral of the Sinc product

Let us consider the following integral $$ B_n = \int_0^\infty \prod_{k=1,3,5,\dots}^n\frac{\sin (x/k)}{x/k}dx $$ By definition, Sinc[x] == Sin[x]/x , therefore B[n_?OddQ] := Integrate[Product[Sinc[x/k], {k, 1, n, 2}], {x, 0, Infinity}] B /@ Range[1, 13, 2] {Pi/2, Pi/2, Pi/2, Pi/2, Pi/2, Pi/2, Pi/2} OK, everything is fine. But... B[15] 467807924713440738696537864469 Pi/935615849440640907310521750000 What's going on? Answer As Eckhard wrote in comments B[n] is the n-th Borwein integral . (The letter B was not accidental :) ) This funny properties of Borwein integrals is related to the Fourier transform of Sinc function FourierTransform[Sinc[x], x, k] 1/2 Sqrt[Pi/2] (Sign[1 - k] + Sign[1 + k]) Plot[%, {k, -2, 2}, Filling -> 0] which is the box function. The result is $\pi/2$ while the sum $$ 1/3+1/5+\dots+1/n $$ B_n = \frac{\pi}{2} - \pi \bigg(\sum_{k=3,5,\ldots}^n\frac{1}{k} -1\biggr)^\frac{n-1}{2}\prod_{k=3,5,\dots}^n\frac{k}{k-1}. $$ For $n=15$ it is equal to $$ \frac{46780...