The small number of some reactant molecules in biological systems formed by living cells can result in dynamical behavior which cannot be captured by traditional deterministic models. In such a problem, a more accurate simulation can be obtained with discrete stochastic simulation (Gillespie’s stochastic simulation algorithm — SSA). Many stochastic realizations are required to capture accurate statistical information of the solution. This carries a very high computational cost. The current generation of graphics processing units (GPU) is well-suited to this task. In this paper we describe our implementation and present some computational experiments illustrating the power of this technology for this important and challenging class of problems.
Arkin, A., Ross, J., and McAdams, H. ( 1998). Stochastic kinetic analysis of developmental pathway bifurcation in phage λ-infected E. Coli cells, Genetics , 149: 1633- 1648.
2.
Blue, J., Beichl, I., and Sullivan, F. ( 1995). Faster Monte Carlo simulations, PhysicalRev. E, 51: 867-868.
3.
Brent, R.P. ( 1992). Uniform random number generators for vector and parallel computers. In proceedings of 5th Australian Supercomputer Conference.
4.
Cao, Y. and Petzold, L. ( 2006). Accuracy limitations and the measurement of errors in the stochastic simulation of chemically reacting systems, J. Comput. Phys., 212: 6-24.
5.
Cao, Y., Li, H., and Petzold, L. ( 2004). Efficient formulation of the stochastic simulation algorithm for chemically reacting systems, J. Phys. Chem., 121: 4059-4067.
6.
Gibson, M. and Bruck, J. ( 2000). Efficient exact stochastic simulation of chemical systems with many species and many channels, J. Phys. Chem., 105: 1876-1889.
7.
Gillespie, D.T. ( 1976). A general method for numerically simulating the stochastic time evolution of coupled chemical reactions, J. Comp. Phys. , 22: 403-434.
8.
Gillespie, D.T. ( 1977). Exact stochastic simulation of coupled chemical reactions , J. Phys. Chem., 81: 2340-2361.
9.
Gillespie, D.T. ( 2001). Approximate accelerated stochastic simulation of chemically reacting systems, J. Chem. Phys., 115: 1716-1733.
Li, H. and Petzold, L. ( 2006). Logarithmic direct method for discrete stochastic simulation of chemically reacting systems. Technical report, Department of Computer Science, University of California, Santa Barbara. http://www.engr.ucsb.edu/~cse
13.
Li, H., Cao, Y., Petzold, L., and Gillespie, D. ( 2007). Algorithms and software for stochastic simulation of biochemical reacting systems, Biotechnology Progress, 24: 56-61.
14.
Li, H., Kolpas, A., Petzold, L., and Moehlis, J. ( 2008). Efficient parallel simulation of an individual-based fish schooling model on a graphics processing unit. In Proceedings of Grace Hopper Celebration of Women in Computing.
15.
Li, H., Kolpas, A., Petzold, L., and Moehlis, J. ( 2009). Parallel simulation for a fish schooling model on a general-purpose graphics processing unit, Concurrency and Computation: Practice and Experience, 21: 725-737.
16.
Mascagni, M. ( 1999). SPRNG: A scalable library for pseudorandom number generation . In Proceedings of the 9th SIAM Conference on Parallel Processing for Scientific Computing, San Antonio, Texas.
17.
Mascagni, M. and Srinivasan., A. ( 2000). SPRNG: A scalable library for pseudorandom number generation . ACM Transactions on Mathematical Software, 26: 436-461.
18.
Matsumoto, M. and Nishimura, T. ( 1998). Mersenne Twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), 8: 3-30.
19.
Matsumoto, M. and Nishimura, T. ( 2000). Dynamic creation of pseudorandom number generators. In Monte Carlo and Quast - Monte Carlo Methods 1998 Edited by H. Niederreiter and J. Spanier.Berlin: Springer-Verlag , pp 56-69.
20.
Matsumoto, M. and Nishimura, T. ( 2002). A nonempirical test on the weight of pseudorandom number generators. In Monte Carlo and quasi-Monte Carlo methods 2000 , edited by K. T. Fang, F. J. Hickernel, and H. Niederreiter , pp. 381- 395. Berlin: Springer-Verlag .
21.
McAdams, H.H. and Arkin, A. ( 1997). Stochastic mechanisms in gene expression, Proc. Natl Acad. Sci. USA, 94: 814- 819.
22.
McColluma, J.M., Peterson, G.D., Cox, C.D., Simpson, M.L., and Samatova, N.F. ( 2005). The sorting direct method for stochastic simulation of biochemical systems with varying reaction execution behavior, J. Comput. Biol. Chem., 30: 39-49.
23.
McGraw, T. and Nadar, M. ( 2007). Stochastic DT-MRI connectivity mapping on the GPU, IEEE Transactions on Visualization and Computer Graphics, 13: 1504-1511.
Nvidia (2008b). NVIDIA CUDA Toolkit and SDK Release 1.0. http://news.developer.nvidia.com/2007/06/nvidia-cudatoo.html
26.
Owens, J.D., Luebke, D., Govindaraju, N., Harris, M., Krüger, J., Lefohn, A.E., and Purcell, T.J. ( 2005). A survey of general-purpose computation on graphics hardware . In Eurographics 2005, State of the Art Reports, pp. 21-51.
27.
Podlozhnyuk, V. ( 2008). Parallel Mersenne Twister. http://developer.download.nvidia.com/compute/cuda/sdk/website/projects/MersenneTwister/doc/MersenneTwister.pdf
28.
Schulze, T.P. ( 2002). Kinetic Monte Carlo simulations with minimal searching , Physical Review E, 65: 036704.
29.
Shnerb, N., Louzoun, Y., Bettelheim, E., and Solomon, S. ( 2000). The importance of being discrete - life always wins on the surface, Proc. Natl Acad. Sci. USA, 97: 10332.
30.
Yoshimi, M., Osana, Y., lwaoka, Y., Funahashi, A., Hiroi, N., Shibata, Y., lwanaga, N., Kitano, H., and Amano, H. ( 2005). The design of scalable stochastic biochemical simulator on FPGA. Proceeding of IEEE International Conference on Field Programmable Technologies (FPT2005), pp. 139-140.
