Solving the chemical master equation for monomolecular reaction systems analytically

The stochastic dynamics of a well-stirred mixture of molecular species interacting through different biochemical reactions can be accurately modelled by the chemical master equation (CME). Research in the biology and scientific computing community has concentrated mostly on the development of numerical techniques to approximate the solution of the CME via many realizations of the associated Markov jump process. The domain of exact and/or efficient methods for directly solving the CME is still widely open, which is due to its large dimension that grows exponentially with the number of molecular species involved. In this article, we present an exact solution formula of the CME for arbitrary initial conditions in the case where the underlying system is governed by monomolecular reactions. The solution can be expressed in terms of the convolution of multinomial and product Poisson distributions with time-dependent parameters evolving according to the traditional reaction-rate equations. This very structured representation allows to deduce easily many properties of the solution. The model class includes many interesting examples. For more complex reaction systems, our results can be seen as a first step towards the construction of new numerical integrators, because solutions to the monomolecular case provide promising ansatz functions for Galerkin-type methods.     

Beyond the chemical master equation: Stochastic chemical kinetics coupled with auxiliary processes

The chemical master equation and its continuum approximations are indispensable tools in the modeling of chemical reaction networks. These are routinely used to capture complex nonlinear phenomena such as multimodality as well as transient events such as first-passage times, that accurately characterise a plethora of biological and chemical processes. However, some mechanisms, such as heterogeneous cellular growth or phenotypic selection at the population level, cannot be represented by the master equation and thus have been tackled separately. In this work, we propose a unifying framework that augments the chemical master equation to capture such auxiliary dynamics, and we develop and analyse a numerical solver that accurately simulates the system dynamics. We showcase these contributions by casting a diverse array of examples from the literature within this framework and applying the solver to both match and extend previous studies. Analytical calculations performed for each example validate our numerical results and benchmark the solver implementation.     

Efficient parametric analysis of the chemical master equation through model order reduction

ABSTRACT: BACKGROUND: Stochastic biochemical reaction networks are commonly modelled by the chemical master equation, and can be simulated as first order linear differential equations through a finite state projection. Due to the very high state space dimension of these equations, numerical simulations are computationally expensive. This is a particular problem for analysis tasks requiring repeated simulations for different parameter values. Such tasks are computationally expensive to the point of infeasibility with the chemical master equation. RESULTS: In this article, we apply parametric model order reduction techniques in order to construct accurate low-dimensional parametric models of the chemical master equation. These surrogate models can be used in various parametric analysis task such as identifiability analysis, parameter estimation, or sensitivity analysis. As biological examples, we consider two models for gene regulation networks, a bistable switch and a network displaying stochastic oscillations. CONCLUSIONS: The results show that the parametric model reduction yields efficient models of stochastic biochemical reaction networks, and that these models can be useful for systems biology applications involving parametric analysis problems such as parameter exploration, optimization, estimation or sensitivity analysis.     

DeepCME: A deep learning framework for computing solution statistics of the chemical master equation

Stochastic models of biomolecular reaction networks are commonly employed in systems and synthetic biology to study the effects of stochastic fluctuations emanating from reactions involving species with low copy-numbers. For such models, the Kolmogorov’s forward equation is called the chemical master equation (CME), and it is a fundamental system of linear ordinary differential equations (ODEs) that describes the evolution of the probability distribution of the random state-vector representing the copy-numbers of all the reacting species. The size of this system is given by the number of states that are accessible by the chemical system, and for most examples of interest this number is either very large or infinite. Moreover, approximations that reduce the size of the system by retaining only a finite number of important chemical states (e.g. those with non-negligible probability) result in high-dimensional ODE systems, even when the number of reacting species is small. Consequently, accurate numerical solution of the CME is very challenging, despite the linear nature of the underlying ODEs. One often resorts to estimating the solutions via computationally intensive stochastic simulations. The goal of the present paper is to develop a novel deep-learning approach for computing solution statistics of high-dimensional CMEs by reformulating the stochastic dynamics using Kolmogorov’s backward equation. The proposed method leverages superior approximation properties of Deep Neural Networks (DNNs) to reliably estimate expectations under the CME solution for several user-defined functions of the state-vector. This method is algorithmically based on reinforcement learning and it only requires a moderate number of stochastic simulations (in comparison to typical simulation-based approaches) to train the “policy function”. This allows not just the numerical approximation of various expectations for the CME solution but also of its sensitivities with respect to all the reaction network parameters (e.g. rate constants). We provide four examples to illustrate our methodology and provide several directions for future research.     

Inferring missing genotypes in large SNP panels using fast nearest-neighbor searches over sliding windows

MOTIVATION: Typical high-throughput genotyping techniques produce numerous missing calls that confound subsequent analyses, such as disease association studies. Common remedies for this problem include removing affected markers and/or samples or, otherwise, imputing the missing data. On small marker sets imputation is frequently based on a vote of the K-nearest-neighbor (KNN) haplotypes, but this technique is neither practical nor justifiable for large datasets. RESULTS: We describe a data structure that supports efficient KNN queries over arbitrarily sized, sliding haplotype windows, and evaluate its use for genotype imputation. The performance of our method enables exhaustive exploration over all window sizes and known sites in large (150K, 8.3M) SNP panels. We also compare the accuracy and performance of our methods with competing imputation approaches. AVAILABILITY: A free open source software package, NPUTE, is available at http://compgen.unc.edu/software, for non-commercial uses.     

General solution of the chemical master equation and modality of marginal distributions for hierarchic first-order reaction networks

Journal of Mathematical Biology - Multimodality is a phenomenon which complicates the analysis of statistical data based exclusively on mean and variance. Here, we present criteria for...     

Expansion of the master equation for a biomolecular selection model

A stochastic model based on Eigen and Schuster's theory of biomolecular self-replication is studied by treating the master equation with the system-size expansion technique. The steady-state results are found to be in good agreement with the previous results and with those derived from the principle of detailed balancing. Multispecies competition and coexistence are studied carefully with the conclusions that a stable steady state is predicted for the former and a metastable state for the latter. The stochastic selection processes are also analyzed and discussed.     

Numerical integration of the master equation in some models of stochastic epidemiology

The processes by which disease spreads in a population of individuals are inherently stochastic. The master equation has proven to be a useful tool for modeling such processes. Unfortunately, solving the master equation analytically is possible only in limited cases (e.g., when the model is linear), and thus numerical procedures or approximation methods must be employed. Available approximation methods, such as the system size expansion method of van Kampen, may fail to provide reliable solutions, whereas current numerical approaches can induce appreciable computational cost. In this paper, we propose a new numerical technique for solving the master equation. Our method is based on a more informative stochastic process than the population process commonly used in the literature. By exploiting the structure of the master equation governing this process, we develop a novel technique for calculating the exact solution of the master equation--up to a desired precision--in certain models of stochastic epidemiology. We demonstrate the potential of our method by solving the master equation associated with the stochastic SIR epidemic model. MATLAB software that implements the methods discussed in this paper is freely available as Supporting Information S1.     

Association mapping via regularized regression analysis of single-nucleotide-polymorphism haplotypes in variable-sized sliding windows

Large-scale haplotype association analysis, especially at the whole-genome level, is still a very challenging task without an optimal solution. In this study, we propose a new approach for haplotype association analysis that is based on a variable-sized sliding-window framework and employs regularized regression analysis to tackle the problem of multiple degrees of freedom in the haplotype test. Our method can handle a large number of haplotypes in association analyses more efficiently and effectively than do currently available approaches. We implement a procedure in which the maximum size of a sliding window is determined by local haplotype diversity and sample size, an attractive feature for large-scale haplotype analyses, such as a whole-genome scan, in which linkage disequilibrium patterns are expected to vary widely. We compare the performance of our method with that of three other methods--a test based on a single-nucleotide polymorphism, a cladistic analysis of haplotypes, and variable-length Markov chains--with use of both simulated and experimental data. By analyzing data sets simulated under different disease models, we demonstrate that our method consistently outperforms the other three methods, especially when the region under study has high haplotype diversity. Built on the regression analysis framework, our method can incorporate other risk-factor information into haplotype-based association analysis, which is becoming an increasingly necessary step for studying common disorders to which both genetic and environmental risk factors contribute.     

Solving chemical problems through the application of evolutionary principles

Molecular evolution has been widely applied in the laboratory to generate novel biological macromolecules. The principles underlying evolution have more recently been used to address problems in the chemical sciences, including the discovery of functional synthetic small molecules, catalysts, materials and new chemical reactions. The application of these principles in dynamic combinatorial chemistry and in efforts involving small molecule-nucleic acid conjugates has facilitated the evaluation of large numbers of candidate structures or reactions for desired characteristics. These early efforts suggest the promise of pairing evolutionary approaches with synthetic chemistry.     

A master equation for a spatial population model with pair interactions

We derive a closed master equation for an individual-based population model in continuous space and time. The model and master equation include Brownian motion, reproduction via binary fission, and an interaction-dependent death rate moderated by a competition kernel. Using simulations we compare this individual-based model with the simplest approximation, the spatial logistic equation. In the limit of strong diffusion the spatial logistic equation is a good approximation to the model. However, in the limit of weak diffusion the spatial logistic equation is inaccurate because of spontaneous clustering driven by reproduction. The weak-diffusion limit can be partially analyzed using an exact solution of the master equation applicable to a competition kernel with infinite range. This analysis shows that in the case of a top-hat kernel, reducing the diffusion can increase the total population. For a Gaussian kernel, reduced diffusion invariably reduces the total population. These theoretical results are confirmed by simulation.     

Analysis of stochastic strategies in bacterial competence: a master equation approach

Competence is a transiently differentiated state that certain bacterial cells reach when faced with a stressful environment. Entrance into competence can be attributed to the excitability of the dynamics governing the genetic circuit that regulates this cellular behavior. Like many biological behaviors, entrance into competence is a stochastic event. In this case cellular noise is responsible for driving the cell from a vegetative state into competence and back. In this work we present a novel numerical method for the analysis of stochastic biochemical events and use it to study the excitable dynamics responsible for competence in Bacillus subtilis. Starting with a Finite State Projection (FSP) solution of the chemical master equation (CME), we develop efficient numerical tools for accurately computing competence probability. Additionally, we propose a new approach for the sensitivity analysis of stochastic events and utilize it to elucidate the robustness properties of the competence regulatory genetic circuit. We also propose and implement a numerical method to calculate the expected time it takes a cell to return from competence. Although this study is focused on an example of cell-differentiation in Bacillus subtilis, our approach can be applied to a wide range of stochastic phenomena in biological systems.     

Turbidimetric studies on microtubule sliding using the stopped-flow-light-scattering method

The turbidity of axonemes during active sliding of microtubules was analysed using the stopped-flow-light-scattering method with high time resolution. Flagella of sea-urchin spermatozoa were demembranated and used after a brief treatment with trypsin. The turbidity of the suspension of flagellar axonemes during ATP-induced disintegration was measured and its time course fitted to a single exponential function which yielded the rate of disintegration, R(1/sec). R coincided well with the velocity of microtubule sliding, V(microM sec) as determined by cinematomicrographic analysis, i.e., R = 0.22 X V, r = 0.9973. It indicates that turbidimetry is a useful method with which to learn the sliding velocity of microtubules. From the dependency of R on temperature, Q10 of the sliding velocity was estimated to be 2.0-2.3 at 43-820 microM of MgATP.     

Reconstruction of the nasal tip using nasalis myocutaneous sliding flaps

An alar island subcutaneous sliding flap is described which, when analyzed, is actually myocutaneous, based on the lower portions of the nasalis muscle. In a series of 47 patients, tip defects 1.25 cm in diameter were reconstructed with a unilateral flap, and defects 2.0 cm in diameter were reconstructed with a bilateral flap. The advantage of the flap lies in aesthetics, which are so important in tip surgery. Not only are the incisions at or parallel with the edges of the lateral crus of the lower lateral cartilage, but also chronic edema and "dog-ears" so common after rotation pedicle flaps are avoided.