Efficient Constant-Time Complexity Algorithm for Stochastic Simulation of Large Reaction Networks

Catalyst: Fast and flexible modeling of reaction networks

We introduce Catalyst.jl, a flexible and feature-filled Julia library for modeling and high-performance simulation of chemical reaction networks (CRNs). Catalyst supports simulating stochastic chemical kinetics (jump process), chemical Langevin equation (stochastic differential equation), and reaction rate equation (ordinary differential equation) representations for CRNs. Through comprehensive benchmarks, we demonstrate that Catalyst simulation runtimes are often one to two orders of magnitude faster than other popular tools. More broadly, Catalyst acts as both a domain-specific language and an intermediate representation for symbolically encoding CRN models as Julia-native objects. This enables a pipeline of symbolically specifying, analyzing, and modifying CRNs; converting Catalyst models to symbolic representations of concrete mathematical models; and generating compiled code for numerical solvers. Leveraging ModelingToolkit.jl and Symbolics.jl, Catalyst models can be analyzed, simplified, and compiled into optimized representations for use in numerical solvers. Finally, we demonstrate Catalyst's broad extensibility and composability by highlighting how it can compose with a variety of Julia libraries, and how existing open-source biological modeling projects have extended its intermediate representation.

Block Search Stochastic Simulation Algorithm (BlSSSA): A Fast Stochastic Simulation Algorithm for Modeling Large Biochemical Networks

Stochastic simulation algorithms are extensively used for exploring stochastic behavior of biochemical pathways/networks. Computational cost of these algorithms is high in simulating real biochemical systems due to their large size, complex structure and stiffness. In order to reduce the computational cost, several algorithms have been developed. It is observed that these algorithms are basically fast in simulating weakly coupled networks. In case of strongly coupled networks, they become slow as their computational cost become high in maintaining complex data structures. Here, we develop Block Search Stochastic Simulation Algorithm (BlSSSA). BlSSSA is not only fast in simulating weakly coupled networks but also fast in simulating strongly coupled and stiff networks. We compare its performance with other existing algorithms using two hypothetical networks, viz., linear chain and colloidal aggregation network, and three real biochemical networks, viz., B cell receptor signaling network, FceRI signaling network and a stiff 1,3-Butadiene Oxidation network. It has been shown that BlSSSA is faster than other algorithms considered in this study.

Cotranscriptional Kinetic Folding of RNA Secondary Structures Including Pseudoknots

Computational prediction of ribonucleic acid (RNA) structures is an important problem in computational structural biology. Studies of RNA structure formation often assume that the process starts from a fully synthesized sequence. Experimental evidence, however, has shown that RNA folds concurrently with its elongation. We investigate RNA secondary structure formation, including pseudoknots, that takes into account the cotranscriptional effects. We propose a single-nucleotide resolution kinetic model of the folding process of RNA molecules, where the polymerase-driven elongation of an RNA strand by a new nucleotide is included as a primitive operation, together with a stochastic simulation method that implements this folding concurrently with the transcriptional synthesis. Numerical case studies show that our cotranscriptional RNA folding model can predict the formation of conformations that are favored in actual biological systems. Our new computational tool can thus provide quantitative predictions and offer useful insights into the kinetics of RNA folding.

Stochastic simulation algorithms for computational systems biology: Exact, approximate, and hybrid methods

Nowadays, mathematical modeling is playing a key role in many different research fields. In the context of system biology, mathematical models and their associated computer simulations constitute essential tools of investigation. Among the others, they provide a way to systematically analyze systems perturbations, develop hypotheses to guide the design of new experimental tests, and ultimately assess the suitability of specific molecules as novel therapeutic targets. To these purposes, stochastic simulation algorithms (SSAs) have been introduced for numerically simulating the time evolution of a well-stirred chemically reacting system by taking proper account of the randomness inherent in such a system. In this work, we review the main SSAs that have been introduced in the context of exact, approximate, and hybrid stochastic simulation. Specifically, we will introduce the direct method (DM), the first reaction method (FRM), the next reaction method (NRM) and the rejection-based SSA (RSSA) in the area of exact stochastic simulation. We will then present the τ-leaping method and the chemical Langevin method in the area of approximate stochastic simulation and an implementation of the hybrid RSSA (HRSSA) in the context of hybrid stochastic-deterministic simulation. Finally, we will consider the model of the sphingolipid metabolism to provide an example of application of SSA to computational system biology by exemplifying how different simulation strategies may unveil different insights into the investigated biological phenomenon. This article is categorized under: Models of Systems Properties and Processes > Mechanistic Models Analytical and Computational Methods > Computational Methods.

Efficient anticorrelated variance reduction for stochastic simulation of biochemical reactions

We investigate the computational challenge of improving the accuracy of the stochastic simulation estimation by inducing negative correlation through the anticorrelated variance reduction technique. A direct application of the technique to the stochastic simulation algorithm (SSA), employing the inverse transformation, is not efficient for simulating large networks because its computational cost is similar to the sum of independent simulation runs. We propose in this study a new algorithm that employs the propensity bounds of reactions, introduced recently in their rejection-based SSA, to correlate and synchronise the trajectories during the simulation. The selection of reaction firings by our approach is exact due to the rejection-based mechanism. In addition, by applying the anticorrelated variance technique to select reaction firings, our approach can induce substantial correlation between realisations, hence reducing the variance of the estimator. The computational advantage of our rejection-based approach in comparison with the traditional inverse transformation is that it only needs to maintain a single data structure storing propensity bounds of reactions, which is updated infrequently, hence achieving better performance.

Incorporating extrinsic noise into the stochastic simulation of biochemical reactions: A comparison of approaches

The stochastic simulation algorithm (SSA) has been widely used for simulating biochemical reaction networks. SSA is able to capture the inherently intrinsic noise of the biological system, which is due to the discreteness of species population and to the randomness of their reciprocal interactions. However, SSA does not consider other sources of heterogeneity in biochemical reaction systems, which are referred to as extrinsic noise. Here, we extend two simulation approaches, namely, the integration-based method and the rejection-based method, to take extrinsic noise into account by allowing the reaction propensities to vary in time and state dependent manner. For both methods, new efficient implementations are introduced and their efficiency and applicability to biological models are investigated. Our numerical results suggest that the rejection-based method performs better than the integration-based method when the extrinsic noise is considered.

A Critical Comparison of Rejection-Based Algorithms for Simulation of Large Biochemical Reaction Networks

The rejection-based simulation technique has been applying to improve the computational efficiency of the stochastic simulation algorithm (SSA) in simulating large reaction networks, which are required for a thorough understanding of biological systems. We compare two recently proposed simulation methods, namely the composition-rejection algorithm (SSA-CR) and the rejection-based SSA (RSSA), aiming for this purpose. We discuss the right interpretation of the rejection-based technique used in these algorithms in order to make an informed choice when dealing with different aspects of biochemical networks. We provide the theoretical analysis as well as the detailed runtime comparison of these algorithms on concrete biological models. We highlight important factors that are omitted in previous analysis of these algorithms. The numerical comparison shows that for reaction networks where the search cost is expensive then SSA-CR is more efficient, and for reaction networks where the update cost is dominant, often the case in practice, then RSSA should be the choice.

Bridging intracellular scales by mechanistic computational models

The impact of intracellular spatial organization beyond classical compartments on processes such as cell signaling is increasingly recognized. A quantitative, mechanistic understanding of cellular systems therefore needs to account for different scales in at least three coordinates: time, molecular abundances, and space. Mechanistic mathematical models may span all these scales, but corresponding multi-scale models need to resolve mechanistic details on small scales while maintaining computational tractability for larger ones. This typically results in models that combine different levels of description: from a microscopic representation of chemical reactions up to continuum dynamics in space and time. We highlight recent progress in bridging these model classes and outline current challenges in multi-scale models such as active transport and dynamic geometries.

Stochastic simulation of biochemical reactions with partial-propensity and rejection-based approaches

We present in this paper a new exact algorithm for improving performance of exact stochastic simulation algorithm. The algorithm is developed on concepts of the partial-propensity and the rejection-based approaches. It factorizes the propensity bounds of reactions and groups factors by common reactant species for selecting next reaction firings. Our algorithm provides favorable computational advantages for simulating of biochemical reaction networks by reducing the cost for selecting the next reaction firing to scale with the number of chemical species and avoiding expensive propensity updates during the simulation. We present the details of our new algorithm and benchmark it on concrete biological models to demonstrate its applicability and efficiency.