| An exact method for stochastic simulation of chemical reaction networks, which accelerates the Stochastic Simulation Algorithm (SSA), is proposed. The present "ER- leap" algorithm is derived from analytic upper and lower bounds on the multi-reaction probabilities sampled by SSA, together with rejection sampling and an adaptive multiplicity for reactions. The algorithm is tested on a number of well-quantified reaction networks and is found experimentally to be very accurate on test problems including a chaotic reaction network. At the same time, ER-leap offers a substantial speed-up over SSA with a simulation time proportional to the 2/3 power of the number of reaction events in a Galton-Watson process. A second algorithm, "HiER-leap", is derived using some of the same principles used in the ER-leap derivation. HiER-leap utilizes a hierarchical organization of reaction channels into tightly coupled "blocks". Large portions of inter-block sampling may be done in parallel. An accept/reject step is used to synchronize across blocks. This method scales well when many reaction channels are present and has desirable asymptotic properties. The algorithm is exact, parallelizable and offers a significant speedup over SSA and ER-leap on certain problems. These two proposed algorithms offer a significant step towards efficient in silico modeling of entire organisms. |
