An adaptive algorithm for simulation of stochastic reaction–diffusion processes

Abstract

We propose an adaptive hybrid method suitable for stochastic simulation of diffusion dominated reaction–diffusion processes. For such systems, simulation of the diffusion requires the predominant part of the computing time. In order to reduce the computational work, the diffusion in parts of the domain is treated macroscopically, in other parts with the tau-leap method and in the remaining parts with Gillespie’s stochastic simulation algorithm (SSA) as implemented in the next subvolume method (NSM). The chemical reactions are handled by SSA everywhere in the computational domain. A trajectory of the process is advanced in time by an operator splitting technique and the timesteps are chosen adaptively. The spatial adaptation is based on estimates of the errors in the tau-leap method and the macroscopic diffusion. The accuracy and efficiency of the method are demonstrated in examples from molecular biology where the domain is discretized by unstructured meshes.

Introduction

The number of molecules of each species in a biological cell is often small and a mesoscopic, stochastic model for the chemical reactions is necessary to explain experimental data [5], [41]. The macroscopic, deterministic equation for the concentrations of the chemical species is the reaction rate equation (RRE). This is an accurate model when the copy numbers are large but this is often not the case e.g. in the nucleus of a cell. Many computational methods have been developed in the last decade for the well stirred mesoscopic, stochastic problem when the distribution of the species in space is ignored. Recently, methods for the space dependent case have appeared.

Continuous time discrete (state) space Markov processes are well established as a mathematical tool to analyze the behavior of biochemical reaction networks in systems biology. Most models assume that the system is well stirred and that the model can be analyzed by solving the chemical master equation (CME) for the probability density function (PDF) or, if the dimension of the model is too high, by simulation of the process with e.g. the stochastic simulation algorithm (SSA) [25]. However, there are scenarios where diffusive transport needs to be included in the model [16], [22], [42]. If the spatial distribution of molecules is important, diffusion can be accounted for by discretizing the domain and allowing species to jump between adjacent computational cells (or subvolumes, compartments, voxels) [23], [33]. Chemical reactions occur between the molecules in each subvolume as in the well stirred case and in this setting the PDF is the solution of the reaction–diffusion master equation (RDME). Also in this case the system can be simulated by a stochastic method [7], [18], [19], [22], [30], [38], [52]. Based on the next reaction method (NRM) [24], the next subvolume method (NSM) [18] is an efficient algorithm for simulation of reaction–diffusion processes and it has been implemented for Cartesian meshes in [28] and for general, unstructured meshes in [14]. Methods for stochastic reaction–diffusion models are compared in [4], [15].

One challenging problem when simulating stochastic models in the well stirred case is stiffness. If a few of the reactions are very fast this leads to very small timesteps in the algorithm and frequent sampling of the fast reaction channels. Often, this is caused by some of the species being present in a much higher copy number than the others for which the stochastic fluctuations are less important. Due to this, it may be difficult to simulate the system on the time scale of the slower, often more interesting dynamics. This has led to the development of many approximate, hybrid and multiscale methods, for examples of these methods and reviews see e.g. [8], [21], [39], [43]. The most popular approximate method in the well stirred case is the tau-leap method [26] and it has also been used for diffusion [46]. It approximates the number of events taking place in a time interval by a Poissonian random variable, and thus several events may be “leaped over” in one timestep.

For systems governed by the RDME, the situation can be even worse. High copy number species, possibly diffusing faster than some of the less abundant species, may render the system very stiff. Almost all events generated by the algorithm will be diffusion events occurring on a short time scale. This problem will inevitably arise if models become more detailed and explicitly include e.g. second messengers or small metabolites. If high concentrations are localized to some region in space and time, which may be the case in models of e.g. transient release of intracellular calcium pools or a step increase in second messenger concentration due to a transient stimulus, any method dealing with the stiffness needs to be adaptive in space and time.

Realizations of a process governed by a RDME are generated on an unstructured mesh in [19]. The diffusion coefficients in the RDME are derived from a finite element discretization of the diffusion operator. This discretization is also the macroscopic approximation of the diffusion. A hybrid method is proposed where the diffusion of some species is advanced macroscopically in all timesteps in the whole computational domain. The inefficiency caused by the diffusion of species present in large numbers in the subvolumes is then reduced considerably. The macroscopic part is coupled to the mesoscopic simulation of the trajectories by operator splitting.

Starting with the framework in [19], we develop in this paper an adaptive, multilevel algorithm that automatically chooses between the mesoscopic NSM, the explicit tau-leap method, and a macroscopic treatment for the diffusion. This is done by using an operator splitting scheme [51] so that we in each timestep can evolve the RDME using a different method in different regions in space. Provided that the copy number is high enough, the tau-leap method is more efficient than SSA and the cost of integration of the macroscopic diffusion equation is negligible compared to the two stochastic methods. The selection of the method to update the degrees of freedom (dofs) in every timestep is based on error estimates for the expected values when diffusion is advanced with tau-leaping [45] or macroscopically and on the risk of a dof becoming negative in a timestep. The same technique is applicable to both structured Cartesian meshes and unstructured meshes. The simulation time can decrease significantly with this approach with full control of the local errors in the approximations. Two different methods are mixed in [46] where the reactions are treated stochastically and the diffusion by a deterministic approximation.

The contents of the paper are as follows. The modeling background and the RDME are presented in Section 2. The adaptive method is proposed and analyzed in Section 3. The space operator is split according to Strang [51] in Section 3.1 and then the space and time adaptive algorithm is described in Sections 3.2 Space adaptivity, 3.3 Timestep selection, 3.4 Algorithm. The computational work is estimated in Section 3.5. The method is first applied to diffusion of one species in two dimensions (2D) in Section 4.1 to illustrate the behavior of the algorithm. Then in Section 4.2 a more realistic model with a domain modeling a yeast cell in three dimensions (3D) is simulated on an unstructured mesh in three scenarios using an extension of the URDME software [14] resulting in considerable savings in computing time in some scenarios.