Parallelising the finite state projection method


  • Vikram Sunkara
  • Markus Hegland



Chemical Master Equation, Finite State Projection Method, Computational Biology


Many realistic mathematical models of biological and chemical systems, such as enzyme cascades and gene regulatory networks, need to include stochasticity. These systems are described as Markov processes and are modelled using the Chemical Master Equation. The Chemical Master Equation is a differential-difference equation (continuous in time and discrete in the state space) for the probability of a certain state at a given time. The state space is the population count of species in the system. A successful method for computing the Chemical Master Equation is the Finite State Projection Method. We give a new algorithm to distribute the Finite State Projection Method method onto multi-core systems. This method is called the Parallel Finite State Projection method. This article also analyses the theory needed for parallelisation of the Chemical Master Equation. References
  • cmepy, Jan 2011.
  • K. Burrage, M. Hegland, S. MacNamara, and R.B. Sidje. A Krylov-based finite state projection algorithm for solving the chemical master equation arising in the discrete modeling of biological systems. In: Langville, A. N., Stewart, W. J. (Eds.), Proceedings of the 150th Markov Anniversary Meeting, Boson Books, pp. 21--38, 2006.
  • S. Engblom. Numerical Solution Methods in Stochastic Chemical Kenetics. PhD thesis, Uppsala University, 2008.
  • M. Hegland, A. Hellander, and P. Lotstedt. Sparse grid and hybrid methods for the chemical master equation. BIT Numerical Mathematics, 48(2):265--283, 2008. doi:10.1007/s10543-008-0174-z
  • M. Khammash and B. Munsky. The finite state projection algorithm for the solution of the chemical master equation. Journal of Chemical Physics, 124(044104):1--12, 2006. doi:10.1063/1.2145882
  • S. MacNamara, A.M. Bersani, K. Burrage, and R.B. Sidje. Stochastic chemical kinetics and the total quasi-steady-state assumption: application to the stochastic simulation algorithm and chemical master equation. Journal of Chemical Physics, 129(095105):1--13, 2008. doi:10.1063/1.2971036
  • V. Sunkara and M. Hegland. An optimal finite state projection method. Procedia Computer Science, 1(1):1579--1586, 2010. ICCS 2010., doi:10.1016/j.procs.2010.04.177





Proceedings Computational Techniques and Applications Conference