^{1}, Philippe Chatelain

^{1}and Petros Koumoutsakos

^{1,a)}

### Abstract

A novel algorithm is proposed for the acceleration of the exact stochastic simulation algorithm by a predefined number of reaction firings (-*leaping*) that may occur across several reaction channels. In the present approach, the numbers of reaction firings are correlated binomial distributions and the sampling procedure is independent of any permutation of the reaction channels. This enables the algorithm to efficiently handle large systems with disparate rates, providing substantial computational savings in certain cases. Several mechanisms for controlling the accuracy and the appearance of negative species are described. The advantages and drawbacks of -*leaping* are assessed by simulations on a number of benchmark problems and the results are discussed in comparison with established methods.

I. INTRODUCTION

II. REACTION LEAPING

A. Background

1. Exact stochastic simulation algorithm

2. Approximate accelerated algorithms: -leaping

B. -leaping: The reaction leaping approach

1. -sampling: independent pointwise variables

2. -sampling: correlated binomial variables

3. -sampling acceleration for systems with disparate rates

4. Discussion

C. Control of

1. Bounding the propensity changes by a fraction of

2. Bounding the relative change in the propensities

3. Bounding the relative change in the molecular population

D. Control of negative species

E. -leaping: Summary

III. NUMERICAL SIMULATIONS

A. Accuracy of -leaping

B. Control of negative species

C. LacZ/LacY model

IV. CONCLUSION

### Key Topics

- Poisson's equation
- 9.0
- Probability theory
- 7.0
- Biochemical reactions
- 5.0
- Sampling theory
- 3.0
- Chain reactions
- 2.0

## Figures

Decaying-dimerizing reaction set [Eq. (30)]: histogram of the distribution of the species for for several values of the accuracy parameter .

Decaying-dimerizing reaction set [Eq. (30)]: histogram of the distribution of the species for for several values of the accuracy parameter .

Decaying-dimerizing reaction set [Eq. (30)]: Cross plots of the computation time, histogram error and control parameter for -leaping (“엯” markers) and -leaping (“▿” markers).

Decaying-dimerizing reaction set [Eq. (30)]: Cross plots of the computation time, histogram error and control parameter for -leaping (“엯” markers) and -leaping (“▿” markers).

Low species reactions [Eq. (32)] speedup of -leaping relative to the SSA vs the relaxation parameter for (×), 0.01 (▿), 0.03 (엯), and 0.05 (+) in linear and logarithmic coordinates.

Low species reactions [Eq. (32)] speedup of -leaping relative to the SSA vs the relaxation parameter for (×), 0.01 (▿), 0.03 (엯), and 0.05 (+) in linear and logarithmic coordinates.

Low species reactions [Eq. (32)]: error on the histogram of species 1 for the modified -leaping relative to the SSA vs the relaxation parameter for (×), 0.01 (▿), 0.03 (엯), and 0.05 (+) in linear and logarithmic coordinates.

Low species reactions [Eq. (32)]: error on the histogram of species 1 for the modified -leaping relative to the SSA vs the relaxation parameter for (×), 0.01 (▿), 0.03 (엯), and 0.05 (+) in linear and logarithmic coordinates.

Low species reactions [Eq. (32)]: contours of the speedup and error of -leaping relative to the SSA vs the relaxation parameters and .

Low species reactions [Eq. (32)]: contours of the speedup and error of -leaping relative to the SSA vs the relaxation parameters and .

Low species reactions [Eq. (32)]: histogram of species 1 for the SSA (엯), -leaping (∗), and -leaping for (◻), 0.08 (▿), and 0.4 (◇).

Low species reactions [Eq. (32)]: histogram of species 1 for the SSA (엯), -leaping (∗), and -leaping for (◻), 0.08 (▿), and 0.4 (◇).

LacZ/LacY model [Kierzek (Ref. 8)]: mean trajectories and standard deviations of four molecular species for the SSA (solid line) and the -leap method with , (dots).

LacZ/LacY model [Kierzek (Ref. 8)]: mean trajectories and standard deviations of four molecular species for the SSA (solid line) and the -leap method with , (dots).

LacZ/LacY model, first cell generation ( to ): plot of the evolution of the number of binomial samples for one -leaping run (, , condition 1 for selection) with (solid) and without (dashed) sorting [step (5)]. When applied, the sorting is made every 10 000 time steps. The straight line indicates the mean value of (equal to 4.1) when the sorting is applied. The value of is monitored every 2500 time steps.

LacZ/LacY model, first cell generation ( to ): plot of the evolution of the number of binomial samples for one -leaping run (, , condition 1 for selection) with (solid) and without (dashed) sorting [step (5)]. When applied, the sorting is made every 10 000 time steps. The straight line indicates the mean value of (equal to 4.1) when the sorting is applied. The value of is monitored every 2500 time steps.

LacZ/LacY model ( to ): histogram distance errors with respect to CPU times for runs. The modified Poisson (◻) algorithm with -selection formula of Ref. 6 [Eq. (3)] is plotted for to by steps of 0.01. The -leaping with condition 3 is plotted for , 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, and 0.75, for fixed values of (indicated under the figures), with (엯) and without (×) sorting.

LacZ/LacY model ( to ): histogram distance errors with respect to CPU times for runs. The modified Poisson (◻) algorithm with -selection formula of Ref. 6 [Eq. (3)] is plotted for to by steps of 0.01. The -leaping with condition 3 is plotted for , 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, and 0.75, for fixed values of (indicated under the figures), with (엯) and without (×) sorting.

## Tables

**Algorithm 1:** **-sampling**

**Algorithm 1:** **-sampling**

**Algorithm 2:** **-sampling**

**Algorithm 2:** **-sampling**

**Algorithm 3:** **-sampling for systems with disparate rates**

**Algorithm 3:** **-sampling for systems with disparate rates**

Low species reactions [Eq. (32)]: speedup relative to the SSA and average number of step per run for the - and -leaping alogrithms with . The values for the original Poisson (OP) and modified Poisson (MP) are taken from (Ref. 5).

Low species reactions [Eq. (32)]: speedup relative to the SSA and average number of step per run for the - and -leaping alogrithms with . The values for the original Poisson (OP) and modified Poisson (MP) are taken from (Ref. 5).

LacZ/LacY model [Kierzek (Ref. 8)]: reaction channels and rates.

LacZ/LacY model [Kierzek (Ref. 8)]: reaction channels and rates.

LacZ/LacY model [Kierzek (Ref. 8)]: speedup relative to the SSA (CPU time SSA/CPU time) for the computation of the first generation .

LacZ/LacY model [Kierzek (Ref. 8)]: speedup relative to the SSA (CPU time SSA/CPU time) for the computation of the first generation .

Article metrics loading...

Full text loading...

Commenting has been disabled for this content