Ever since Gillespie blessed the world by giving us the SSA (Stochastic Simulation Algorithm) there has been countless attempts to improve its computational efficiency. A few of these algorithms are exact, just like Gillespie’s SSA, (exact SSAs simulate every reactive event) the large majority of the SSA improvements are approximative methods. These methods achieve an increased computational efficiency by attempting to leap over “reaction-bundles”, so called tau-leap (i.e. they do not attempt to track every single event one by one). Below is a figure providing an incomplete summary of various implementations based on Gillespie’s original SSA procedure.
The optimized direct methods are all exact methods that are mathematically equivalent to the Direct method (Gillespie’s original SSA implementation). The next big breakthrough came in 2001 when Gillespie introduced the Explicit tau-leap method that since has given rise to several improved versions addressing some of the problems in the original tau-leap method. The next frontier was the development of SSA implementations that are robust for stiff systems (i.e. systems that are characterized by well-separated fast and slow dynamical modes, the fastest of which is stable). Gillespie’s hat trick was the development of the Implicit tau-leap method, followed by the Slow-scale simulation algorithm. The current frontier is the development of adaptive algorithms SSA implementations that minimize the computational time while appropriately managing idiosyncrasies of the specific system, e.g. stiffness.
All the “improved” SSA implementations do not imply that there is anything wrong with the original SSA procedure by Gillespie – on the contrary, the exact SSA always works, e.g. system stiffness is a non issue. The catch is that you have to have time on your hands.
hello there,
i’m an engineering student, and quite new to applied statistics and matlab. but i’m supposed to write a simple program to implement the Gillespie SSA algorithm for simple reactions. but i’m at loss at how to do so and most importantly, how do i start?
thanks. hope to hear from soon…
The direct method by Gillespie is simple and nice and short. Most SSA papers outline this method. I would recommend the following:
Gillespie DT (1976). “A General Method for Numerically Simulating the Stochastic Time
Evolution of Coupled Chemical Reactions.” Journal of Computational Physics, 22, 403–
434.
and
Gillespie DT (2007). “Stochastic Simulation of Chemical Kinetics.” Annual Review of Physical
Chemistry, 58, 35–55.
You could also study someone else’s code, e.g. my R package (GillespieSSA) or the StochKit library (in C). If you are using MatLab it is also worth noting that there is a tool box available that implements the SSA (don’t remember what it is called though).
Hope this helps.
Pingback: What should this blog be about? « Mario’s Entangled Bank