Hybrid simulation of cellular behavior

MOTIVATION: To be valuable to biological or biomedical research, in silico methods must be scaled to complex pathways and large numbers of interacting molecular species. The correct method for performing such simulations, discrete event simulation by Monte Carlo generation, is computationally costly for large complex systems. Approximation of molecular behavior by continuous models fails to capture stochastic behavior that is essential to many biological phenomena. RESULTS: We present a novel approach to building hybrid simulations in which some processes are simulated discretely, while other processes are handled in a continuous simulation by differential equations. This approach preserves the stochastic behavior of cellular pathways, yet enables scaling to large populations of molecules. We present an algorithm for synchronizing data in a hybrid simulation and discuss the trade-offs in such simulation. We have implemented the hybrid simulation algorithm and have validated it by simulating the statistical behavior of the well-known lambda phage switch. Hybrid simulation provides a new method for exploring the sources and nature of stochastic behavior in cells.     

A hybrid multiscale Monte Carlo algorithm (HyMSMC) to cope with disparity in time scales and species populations in intracellular networks

Background  

The fundamental role that intrinsic stochasticity plays in cellular functions has been shown via numerous computational and experimental studies. In the face of such evidence, it is important that intracellular networks are simulated with stochastic algorithms that can capture molecular fluctuations. However, separation of time scales and disparity in species population, two common features of intracellular networks, make stochastic simulation of such networks computationally prohibitive. While recent work has addressed each of these challenges separately, a generic algorithm that can simultaneously tackle disparity in time scales and population scales in stochastic systems is currently lacking. In this paper, we propose the hybrid, multiscale Monte Carlo (HyMSMC) method that fills in this void.     

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.     

A method for estimating stochastic noise in large genetic regulatory networks

MOTIVATION: Genetic regulatory networks are often affected by stochastic noise, due to the low number of molecules taking part in certain reactions. The networks can be simulated using stochastic techniques that model each reaction as a stochastic event. As models become increasingly large and sophisticated, however, the solution time can become excessive; particularly if one wishes to determine the effect on noise of changes to a series of parameters, or the model structure. Methods are therefore required to rapidly estimate stochastic noise. RESULTS: This paper presents an algorithm, based on error growth techniques from non-linear dynamics, to rapidly estimate the noise characteristics of genetic networks of arbitrary size. The method can also be used to determine analytical solutions for simple sub-systems. It is demonstrated on a number of cases, including a prototype model of the galactose regulatory pathway in yeast. AVAILABILITY: A software tool which incorporates the algorithm is available for use as part of the stochastic simulation package Dizzy. It is available for download at http://labs.systemsbiology.net/bolouri/software/Dizzy/ CONTACT: dorrell@systemsbiology.org SUPPLEMENTARY INFORMATION: A conceptual model of the regulatory part of the galactose utilization pathway in yeast, used as an example in the paper, is available at http://labs.systemsbiology.net/bolouri/models/galconcept.dizzy     

Stochastic simulation GUI for biochemical networks

MOTIVATION: This article describes the development of a useful graphical user interface for stochastic simulation of biochemical networks which allows model builders to run stochastic simulations of their models and perform statistical analysis on the results. These include the construction of correlations, power-spectral densities and transfer functions between selected inputs and outputs. AVAILABILITY: The software is licensed under the BSD open source license and is available at http://sourceforge.net/projects/jdesigner. In addition, a more detailed account of the algorithms employed in the tool can be found at the Wiki at http://www.sys-bio.org/sbwWiki. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.     

Multi-dimensional, mesoscopic Monte Carlo simulations of inhomogeneous reaction-drift-diffusion systems on graphics-processing units

For many biological applications, a macroscopic (deterministic) treatment of reaction-drift-diffusion systems is insufficient. Instead, one has to properly handle the stochastic nature of the problem and generate true sample paths of the underlying probability distribution. Unfortunately, stochastic algorithms are computationally expensive and, in most cases, the large number of participating particles renders the relevant parameter regimes inaccessible. In an attempt to address this problem we present a genuine stochastic, multi-dimensional algorithm that solves the inhomogeneous, non-linear, drift-diffusion problem on a mesoscopic level. Our method improves on existing implementations in being multi-dimensional and handling inhomogeneous drift and diffusion. The algorithm is well suited for an implementation on data-parallel hardware architectures such as general-purpose graphics processing units (GPUs). We integrate the method into an operator-splitting approach that decouples chemical reactions from the spatial evolution. We demonstrate the validity and applicability of our algorithm with a comprehensive suite of standard test problems that also serve to quantify the numerical accuracy of the method. We provide a freely available, fully functional GPU implementation. Integration into Inchman, a user-friendly web service, that allows researchers to perform parallel simulations of reaction-drift-diffusion systems on GPU clusters is underway.     

Dynamic partitioning for hybrid simulation of the bistable HIV-1 transactivation network

MOTIVATION: The stochastic kinetics of a well-mixed chemical system, governed by the chemical Master equation, can be simulated using the exact methods of Gillespie. However, these methods do not scale well as systems become more complex and larger models are built to include reactions with widely varying rates, since the computational burden of simulation increases with the number of reaction events. Continuous models may provide an approximate solution and are computationally less costly, but they fail to capture the stochastic behavior of small populations of macromolecules. RESULTS: In this article we present a hybrid simulation algorithm that dynamically partitions the system into subsets of continuous and discrete reactions, approximates the continuous reactions deterministically as a system of ordinary differential equations (ODE) and uses a Monte Carlo method for generating discrete reaction events according to a time-dependent propensity. Our approach to partitioning is improved such that we dynamically partition the system of reactions, based on a threshold relative to the distribution of propensities in the discrete subset. We have implemented the hybrid algorithm in an extensible framework, utilizing two rigorous ODE solvers to approximate the continuous reactions, and use an example model to illustrate the accuracy and potential speedup of the algorithm when compared with exact stochastic simulation. AVAILABILITY: Software and benchmark models used for this publication can be made available upon request from the authors.     

A Population Density Approach That Facilitates Large-Scale Modeling of Neural Networks: Analysis and an Application to Orientation Tuning

We explore a computationally efficient method of simulating realistic networks of neurons introduced by Knight, Manin, and Sirovich (1996) in which integrate-and-fire neurons are grouped into large populations of similar neurons. For each population, we form a probability density that represents the distribution of neurons over all possible states. The populations are coupled via stochastic synapses in which the conductance of a neuron is modulated according to the firing rates of its presynaptic populations. The evolution equation for each of these probability densities is a partial differential-integral equation, which we solve numerically. Results obtained for several example networks are tested against conventional computations for groups of individual neurons.We apply this approach to modeling orientation tuning in the visual cortex. Our population density model is based on the recurrent feedback model of a hypercolumn in cat visual cortex of Somers et al. (1995). We simulate the response to oriented flashed bars. As in the Somers model, a weak orientation bias provided by feed-forward lateral geniculate input is transformed by intracortical circuitry into sharper orientation tuning that is independent of stimulus contrast.The population density approach appears to be a viable method for simulating large neural networks. Its computational efficiency overcomes some of the restrictions imposed by computation time in individual neuron simulations, allowing one to build more complex networks and to explore parameter space more easily. The method produces smooth rate functions with one pass of the stimulus and does not require signal averaging. At the same time, this model captures the dynamics of single-neuron activity that are missed in simple firing-rate models.     

Network-based analysis of stochastic SIR epidemic models with random and proportionate mixing

In this paper, we outline the theory of epidemic percolation networks and their use in the analysis of stochastic susceptible-infectious-removed (SIR) epidemic models on undirected contact networks. We then show how the same theory can be used to analyze stochastic SIR models with random and proportionate mixing. The epidemic percolation networks for these models are purely directed because undirected edges disappear in the limit of a large population. In a series of simulations, we show that epidemic percolation networks accurately predict the mean outbreak size and probability and final size of an epidemic for a variety of epidemic models in homogeneous and heterogeneous populations. Finally, we show that epidemic percolation networks can be used to re-derive classical results from several different areas of infectious disease epidemiology. In an Appendix, we show that an epidemic percolation network can be defined for any time-homogeneous stochastic SIR model in a closed population and prove that the distribution of outbreak sizes given the infection of any given node in the SIR model is identical to the distribution of its out-component sizes in the corresponding probability space of epidemic percolation networks. We conclude that the theory of percolation on semi-directed networks provides a very general framework for the analysis of stochastic SIR models in closed populations.     

Modeling biological systems using Dynetica--a simulator of dynamic networks

We present Dynetica, a user-friendly simulator of dynamic networks for constructing, visualizing, and analyzing kinetic models of biological systems. In addition to generic reaction networks, Dynetica facilitates construction of models of genetic networks, where many reactions are gene expression and interactions among gene products. Further, it integrates the capability of conducting both deterministic and stochastic simulations. AVAILABILITY AND SUPPLEMENTARY INFORMATION: Dynetica 1.0, example models, and the user's guide are available at http://www.its.caltech.edu/~you/Dynetica/Dynetica_page.htm     

Detecting conserved interaction patterns in biological networks.

Molecular interaction data plays an important role in understanding biological processes at a modular level by providing a framework for understanding cellular organization, functional hierarchy, and evolutionary conservation. As the quality and quantity of network and interaction data increases rapidly, the problem of effectively analyzing this data becomes significant. Graph theoretic formalisms, commonly used for these analysis tasks, often lead to computationally hard problems due to their relation to subgraph isomorphism. This paper presents an innovative new algorithm, MULE, for detecting frequently occurring patterns and modules in biological networks. Using an innovative graph simplification technique based on ortholog contraction, which is ideally suited to biological networks, our algorithm renders these problems computationally tractable and scalable to large numbers of networks. We show, experimentally, that our algorithm can extract frequently occurring patterns in metabolic pathways and protein interaction networks from the KEGG, DIP, and BIND databases within seconds. When compared to existing approaches, our graph simplification technique can be viewed either as a pruning heuristic, or a closely related, but computationally simpler task. When used as a pruning heuristic, we show that our technique reduces effective graph sizes significantly, accelerating existing techniques by several orders of magnitude! Indeed, for most of the test cases, existing techniques could not even be applied without our pruning step. When used as a stand-alone analysis technique, MULE is shown to convey significant biological insights at near-interactive rates. The software, sample input graphs, and detailed results for comprehensive analysis of nine eukaryotic PPI networks are available at www.cs.purdue.edu/homes/koyuturk/mule.     

Analysing georeferenced population genetics data with Geneland: a new algorithm to deal with null alleles and a friendly graphical user interface

We introduce a new algorithm to account for the presence of null alleles in inferences of populations clusters from individual multilocus genetic data. We show by simulations that the presence of null alleles can affect the accuracy of inferences if not properly accounted for and that our algorithm improve signficantly their accuracy. AVAILABILITY: This new algorithm is implemented in the program Geneland. It is freely available under GNU public license as an R package on the Comprehensive R Archive Network. It now includes a fully clickable graphical interface. Informations on how to get the software are available on folk.uio.no/gillesg/Geneland.html     

Stochastic simulations of pattern formation in excitable media

We present a method for mesoscopic, dynamic Monte Carlo simulations of pattern formation in excitable reaction-diffusion systems. Using a two-level parallelization approach, our simulations cover the whole range of the parameter space, from the noise-dominated low-particle number regime to the quasi-deterministic high-particle number limit. Three qualitatively different case studies are performed that stand exemplary for the wide variety of excitable systems. We present mesoscopic stochastic simulations of the Gray-Scott model, of a simplified model for intracellular Ca[Formula: see text] oscillations and, for the first time, of the Oregonator model. We achieve simulations with up to [Formula: see text] particles. The software and the model files are freely available and researchers can use the models to reproduce our results or adapt and refine them for further exploration.     

Conservation analysis of large biochemical networks

MOTIVATION: Large biochemical networks pose a unique challenge from the point of view of evaluating conservation laws. The computational problem in most cases exceeds the capability of available software tools, often resulting in inaccurate computation of the number and form of conserved cycles. Such errors have profound effects on subsequent calculations, particularly in the evaluation of the Jacobian which is a critical quantity in many other calculations. The goal of this paper is to outline a new algorithm that is computationally efficient and robust at extracting the correct conservation laws for very large biochemical networks. RESULTS: We show that our algorithm can perform the conservation analysis of large biochemical networks, and can evaluate the correct conserved cycles when compared with other similar software tools. Biochemical simulators such as Jarnac and COPASI are successful at extracting only a subset of the conservation laws that our algorithm can. This is illustrated with examples for some large networks which show the advantages of our method.     

Estimation of Parameters for Macroparasite Population Evolution Using Approximate Bayesian Computation

Summary We estimate the parameters of a stochastic process model for a macroparasite population within a host using approximate Bayesian computation (ABC). The immunity of the host is an unobserved model variable and only mature macroparasites at sacrifice of the host are counted. With very limited data, process rates are inferred reasonably precisely. Modeling involves a three variable Markov process for which the observed data likelihood is computationally intractable. ABC methods are particularly useful when the likelihood is analytically or computationally intractable. The ABC algorithm we present is based on sequential Monte Carlo, is adaptive in nature, and overcomes some drawbacks of previous approaches to ABC. The algorithm is validated on a test example involving simulated data from an autologistic model before being used to infer parameters of the Markov process model for experimental data. The fitted model explains the observed extra‐binomial variation in terms of a zero‐one immunity variable, which has a short‐lived presence in the host.     

An Efficient Steady-State Analysis Method for Large Boolean Networks with High Maximum Node Connectivity

Boolean networks have been widely used to model biological processes lacking detailed kinetic information. Despite their simplicity, Boolean network dynamics can still capture some important features of biological systems such as stable cell phenotypes represented by steady states. For small models, steady states can be determined through exhaustive enumeration of all state transitions. As the number of nodes increases, however, the state space grows exponentially thus making it difficult to find steady states. Over the last several decades, many studies have addressed how to handle such a state space explosion. Recently, increasing attention has been paid to a satisfiability solving algorithm due to its potential scalability to handle large networks. Meanwhile, there still lies a problem in the case of large models with high maximum node connectivity where the satisfiability solving algorithm is known to be computationally intractable. To address the problem, this paper presents a new partitioning-based method that breaks down a given network into smaller subnetworks. Steady states of each subnetworks are identified by independently applying the satisfiability solving algorithm. Then, they are combined to construct the steady states of the overall network. To efficiently apply the satisfiability solving algorithm to each subnetwork, it is crucial to find the best partition of the network. In this paper, we propose a method that divides each subnetwork to be smallest in size and lowest in maximum node connectivity. This minimizes the total cost of finding all steady states in entire subnetworks. The proposed algorithm is compared with others for steady states identification through a number of simulations on both published small models and randomly generated large models with differing maximum node connectivities. The simulation results show that our method can scale up to several hundreds of nodes even for Boolean networks with high maximum node connectivity. The algorithm is implemented and available at http://cps.kaist.ac.kr/∼ckhong/tools/download/PAD.tar.gz.     

Coupled Stochastic Spatial and Non-Spatial Simulations of ErbB1 Signaling Pathways Demonstrate the Importance of Spatial Organization in Signal Transduction

Background

The ErbB family of receptors activates intracellular signaling pathways that control cellular proliferation, growth, differentiation and apoptosis. Given these central roles, it is not surprising that overexpression of the ErbB receptors is often associated with carcinogenesis. Therefore, extensive laboratory studies have been devoted to understanding the signaling events associated with ErbB activation.

Methodology/Principal Findings

Systems biology has contributed significantly to our current understanding of ErbB signaling networks. However, although computational models have grown in complexity over the years, little work has been done to consider the spatial-temporal dynamics of receptor interactions and to evaluate how spatial organization of membrane receptors influences signaling transduction. Herein, we explore the impact of spatial organization of the epidermal growth factor receptor (ErbB1/EGFR) on the initiation of downstream signaling. We describe the development of an algorithm that couples a spatial stochastic model of membrane receptors with a nonspatial stochastic model of the reactions and interactions in the cytosol. This novel algorithm provides a computationally efficient method to evaluate the effects of spatial heterogeneity on the coupling of receptors to cytosolic signaling partners.

Conclusions/Significance

Mathematical models of signal transduction rarely consider the contributions of spatial organization due to high computational costs. A hybrid stochastic approach simplifies analyses of the spatio-temporal aspects of cell signaling and, as an example, demonstrates that receptor clustering contributes significantly to the efficiency of signal propagation from ligand-engaged growth factor receptors.     

A Graph Algorithmic Approach to Separate Direct from Indirect Neural Interactions

Network graphs have become a popular tool to represent complex systems composed of many interacting subunits; especially in neuroscience, network graphs are increasingly used to represent and analyze functional interactions between multiple neural sources. Interactions are often reconstructed using pairwise bivariate analyses, overlooking the multivariate nature of interactions: it is neglected that investigating the effect of one source on a target necessitates to take all other sources as potential nuisance variables into account; also combinations of sources may act jointly on a given target. Bivariate analyses produce networks that may contain spurious interactions, which reduce the interpretability of the network and its graph metrics. A truly multivariate reconstruction, however, is computationally intractable because of the combinatorial explosion in the number of potential interactions. Thus, we have to resort to approximative methods to handle the intractability of multivariate interaction reconstruction, and thereby enable the use of networks in neuroscience. Here, we suggest such an approximative approach in the form of an algorithm that extends fast bivariate interaction reconstruction by identifying potentially spurious interactions post-hoc: the algorithm uses interaction delays reconstructed for directed bivariate interactions to tag potentially spurious edges on the basis of their timing signatures in the context of the surrounding network. Such tagged interactions may then be pruned, which produces a statistically conservative network approximation that is guaranteed to contain non-spurious interactions only. We describe the algorithm and present a reference implementation in MATLAB to test the algorithm’s performance on simulated networks as well as networks derived from magnetoencephalographic data. We discuss the algorithm in relation to other approximative multivariate methods and highlight suitable application scenarios. Our approach is a tractable and data-efficient way of reconstructing approximative networks of multivariate interactions. It is preferable if available data are limited or if fully multivariate approaches are computationally infeasible.