Sliding Window Abstraction for Infinite Markov Chains

Noise has many roles in biological function, including generation of errors in DNA replication leading to mutation and evolution, noise-driven divergence of cell fates, noise-induced amplification of signals, and maintenance of the quantitative individuality of cells. Yet there is order to the behaviour and development of cells. They operate within strict parameters and in many cases this behaviour seems robust, implying that noise is largely filtered by the system. How can we explain the use, rejection and sensitivity to noise that is found in biological systems? An exploration of the sources and consequences of noise calls for the use of stochastic models.

This article introduces the finite state projection (FSP) method for use in the stochastic analysis of chemically reacting systems. One can describe the chemical populations of such systems with probability density vectors that evolve according to a set of linear ordinary differential equations known as the chemical master equation (CME). Unlike Monte Carlo methods such as the stochastic simulation algorithm (SSA) or tau leaping, the FSP directly solves or approximates the solution of the CME. If the CME describes a system that has a finite number of distinct population vectors, the FSP method provides an exact analytical solution. When an infinite or extremely large number of population variations is possible, the state space can be truncated, and the FSP method provides a certificate of accuracy for how closely the truncated space approximation matches the true solution. The proposed FSP algorithm systematically increases the projection space in order to meet prespecified tolerance in the total probability density error. For any system in which a sufficiently accurate FSP exists, the FSP algorithm is shown to converge in a finite number of steps. The FSP is utilized to solve two examples taken from the field of systems biology, and comparisons are made between the FSP, the SSA, and tau leaping algorithms. In both examples, the FSP outperforms the SSA in terms of accuracy as well as computational efficiency. Furthermore, due to very small molecular counts in these particular examples, the FSP also performs far more effectively than tau leaping methods.