1
|
Mjolsness E. Explicit Calculation of Structural Commutation Relations for Stochastic and Dynamical Graph Grammar Rule Operators in Biological Morphodynamics. FRONTIERS IN SYSTEMS BIOLOGY 2022; 2:898858. [PMID: 36712785 PMCID: PMC9879069 DOI: 10.3389/fsysb.2022.898858] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Indexed: 02/02/2023]
Abstract
Many emergent, non-fundamental models of complex systems can be described naturally by the temporal evolution of spatial structures with some nontrivial discretized topology, such as a graph with suitable parameter vectors labeling its vertices. For example, the cytoskeleton of a single cell, such as the cortical microtubule network in a plant cell or the actin filaments in a synapse, comprises many interconnected polymers whose topology is naturally graph-like and dynamic. The same can be said for cells connected dynamically in a developing tissue. There is a mathematical framework suitable for expressing such emergent dynamics, "stochastic parameterized graph grammars," composed of a collection of the graph- and parameter-altering rules, each of which has a time-evolution operator that suitably moves probability. These rule-level operators form an operator algebra, much like particle creation/annihilation operators or Lie group generators. Here, we present an explicit and constructive calculation, in terms of elementary basis operators and standard component notation, of what turns out to be a general combinatorial expression for the operator algebra that reduces products and, therefore, commutators of graph grammar rule operators to equivalent integer-weighted sums of such operators. We show how these results extend to "dynamical graph grammars," which include rules that bear local differential equation dynamics for some continuous-valued parameters. Commutators of such time-evolution operators have analytic uses, including deriving efficient simulation algorithms and approximations and estimating their errors. The resulting formalism is complementary to spatial models in the form of partial differential equations or stochastic reaction-diffusion processes. We discuss the potential application of this framework to the remodeling dynamics of the microtubule cytoskeleton in cortical microtubule networks relevant to plant development and of the actin cytoskeleton in, for example, a growing or shrinking synaptic spine head. Both cytoskeletal systems underlie biological morphodynamics.
Collapse
|
2
|
Hellander S, Hellander A. Hierarchical algorithm for the reaction-diffusion master equation. J Chem Phys 2020; 152:034104. [PMID: 31968960 PMCID: PMC6964990 DOI: 10.1063/1.5095075] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/19/2023] Open
Abstract
We have developed an algorithm coupling mesoscopic simulations on different levels in a hierarchy of Cartesian meshes. Based on the multiscale nature of the chemical reactions, some molecules in the system will live on a fine-grained mesh, while others live on a coarse-grained mesh. By allowing molecules to transfer from the fine levels to the coarse levels when appropriate, we show that we can save up to three orders of magnitude of computational time compared to microscopic simulations or highly resolved mesoscopic simulations, without losing significant accuracy. We demonstrate this in several numerical examples with systems that cannot be accurately simulated with a coarse-grained mesoscopic model.
Collapse
Affiliation(s)
- Stefan Hellander
- Department of Information Technology, Uppsala University, Box 337, SE-755 01 Uppsala, Sweden
| | - Andreas Hellander
- Department of Information Technology, Uppsala University, Box 337, SE-755 01 Uppsala, Sweden
| |
Collapse
|
3
|
Lötstedt P. The Linear Noise Approximation for Spatially Dependent Biochemical Networks. Bull Math Biol 2019; 81:2873-2901. [PMID: 29644520 PMCID: PMC6677697 DOI: 10.1007/s11538-018-0428-0] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/09/2018] [Accepted: 03/29/2018] [Indexed: 10/26/2022]
Abstract
An algorithm for computing the linear noise approximation (LNA) of the reaction-diffusion master equation (RDME) is developed and tested. The RDME is often used as a model for biochemical reaction networks. The LNA is derived for a general discretization of the spatial domain of the problem. If M is the number of chemical species in the network and N is the number of nodes in the discretization in space, then the computational work to determine approximations of the mean and the covariances of the probability distributions is proportional to [Formula: see text] in a straightforward implementation. In our LNA algorithm, the work is proportional to [Formula: see text]. Since N usually is larger than M, this is a significant reduction. The accuracy of the approximation in the algorithm is estimated analytically and evaluated in numerical experiments.
Collapse
Affiliation(s)
- Per Lötstedt
- Division of Scientific Computing, Department of Information Technology, Uppsala University, SE-75105, Uppsala, Sweden.
| |
Collapse
|
4
|
Brian D, Bruno J, Zhen L, Tau-Mu Y, Linda P. A hybrid smoothed dissipative particle dynamics (SDPD) spatial stochastic simulation algorithm (sSSA) for advection-diffusion-reaction problems. JOURNAL OF COMPUTATIONAL PHYSICS 2019; 378:1-17. [PMID: 31031417 PMCID: PMC6481948 DOI: 10.1016/j.jcp.2018.10.043] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/09/2023]
Abstract
We have developed a new algorithm which merges discrete stochastic simulation, using the spatial stochastic simulation algorithm (sSSA), with the particle based fluid dynamics simulation framework of smoothed dissipative particle dynamics (SDPD). This hybrid algorithm enables discrete stochastic simulation of spatially resolved chemically reacting systems on a mesh-free dynamic domain with a Lagrangian frame of reference. SDPD combines two popular mesoscopic techniques: smoothed particle hydrodynamics and dissipative particle dynamics (DPD), linking the macroscopic and mesoscopic hydrodynamics effects of these two methods. We have implemented discrete stochastic simulation using the reaction-diffusion master equations (RDME) formalism, and deterministic reaction-diffusion equations based on the SDPD method. We validate the new method by comparing our results to four canonical models, and demonstrate the versatility of our method by simulating a flow containing a chemical gradient past a yeast cell in a microfluidics chamber.
Collapse
Affiliation(s)
- Drawert Brian
- Department of Computer Science, University of North Carolina at Asheville, Asheville, North Carolina, 28804, USA
| | - Jacob Bruno
- Department of Mechanical Engineering, University of California-Santa Barbara, Santa Barbara, California, 93106, USA
| | - Li Zhen
- Division of Applied Mathematics, Brown University, Providence, Rhode Island 02912, USA
| | - Yi Tau-Mu
- Department of Molecular, Cellular, and Developmental Biology, University of California-Santa Barbara, Santa Barbara, California 93106, USA
| | - Petzold Linda
- Department of Mechanical Engineering, University of California-Santa Barbara, Santa Barbara, California, 93106, USA
- Department of Computer Science, University of California-Santa Barbara, Santa Barbara, California, 93106, USA
| |
Collapse
|
5
|
Kim C, Nonaka A, Bell JB, Garcia AL, Donev A. Stochastic simulation of reaction-diffusion systems: A fluctuating-hydrodynamics approach. J Chem Phys 2018; 146:124110. [PMID: 28388111 DOI: 10.1063/1.4978775] [Citation(s) in RCA: 13] [Impact Index Per Article: 2.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/12/2023] Open
Abstract
We develop numerical methods for stochastic reaction-diffusion systems based on approaches used for fluctuatinghydrodynamics (FHD). For hydrodynamicsystems, the FHD formulation is formally described by stochastic partial differential equations (SPDEs). In the reaction-diffusion systems we consider, our model becomes similar to the reaction-diffusion master equation (RDME) description when our SPDEs are spatially discretized and reactions are modeled as a source term having Poissonfluctuations. However, unlike the RDME, which becomes prohibitively expensive for an increasing number of molecules, our FHD-based description naturally extends from the regime where fluctuations are strong, i.e., each mesoscopic cell has few (reactive) molecules, to regimes with moderate or weak fluctuations, and ultimately to the deterministic limit. By treating diffusion implicitly, we avoid the severe restriction on time step size that limits all methods based on explicit treatments of diffusion and construct numerical methods that are more efficient than RDME methods, without compromising accuracy. Guided by an analysis of the accuracy of the distribution of steady-state fluctuations for the linearized reaction-diffusion model, we construct several two-stage (predictor-corrector) schemes, where diffusion is treated using a stochastic Crank-Nicolson method, and reactions are handled by the stochastic simulation algorithm of Gillespie or a weakly second-order tau leaping method. We find that an implicit midpoint tau leaping scheme attains second-order weak accuracy in the linearized setting and gives an accurate and stable structure factor for a time step size of an order of magnitude larger than the hopping time scale of diffusing molecules. We study the numerical accuracy of our methods for the Schlögl reaction-diffusion model both in and out of thermodynamic equilibrium. We demonstrate and quantify the importance of thermodynamicfluctuations to the formation of a two-dimensional Turing-like pattern and examine the effect of fluctuations on three-dimensional chemical front propagation. By comparing stochastic simulations to deterministic reaction-diffusion simulations, we show that fluctuations accelerate pattern formation in spatially homogeneous systems and lead to a qualitatively different disordered pattern behind a traveling wave.
Collapse
Affiliation(s)
- Changho Kim
- Computational Research Division, Lawrence Berkeley National Laboratory, 1 Cyclotron Road, Berkeley, California 94720, USA
| | - Andy Nonaka
- Computational Research Division, Lawrence Berkeley National Laboratory, 1 Cyclotron Road, Berkeley, California 94720, USA
| | - John B Bell
- Computational Research Division, Lawrence Berkeley National Laboratory, 1 Cyclotron Road, Berkeley, California 94720, USA
| | - Alejandro L Garcia
- Department of Physics and Astronomy, San Jose State University, 1 Washington Square, San Jose, California 95192, USA
| | - Aleksandar Donev
- Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, New York 10012, USA
| |
Collapse
|
6
|
Hepburn I, Chen W, De Schutter E. Accurate reaction-diffusion operator splitting on tetrahedral meshes for parallel stochastic molecular simulations. J Chem Phys 2017; 145:054118. [PMID: 27497550 DOI: 10.1063/1.4960034] [Citation(s) in RCA: 13] [Impact Index Per Article: 1.9] [Reference Citation Analysis] [Abstract] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/14/2022] Open
Abstract
Spatial stochastic molecular simulations in biology are limited by the intense computation required to track molecules in space either in a discrete time or discrete space framework, which has led to the development of parallel methods that can take advantage of the power of modern supercomputers in recent years. We systematically test suggested components of stochastic reaction-diffusion operator splitting in the literature and discuss their effects on accuracy. We introduce an operator splitting implementation for irregular meshes that enhances accuracy with minimal performance cost. We test a range of models in small-scale MPI simulations from simple diffusion models to realistic biological models and find that multi-dimensional geometry partitioning is an important consideration for optimum performance. We demonstrate performance gains of 1-3 orders of magnitude in the parallel implementation, with peak performance strongly dependent on model specification.
Collapse
Affiliation(s)
- I Hepburn
- Computational Neuroscience Unit, Okinawa Institute of Science and Technology Graduate University, Onna, Okinawa 904 0495, Japan
| | - W Chen
- Computational Neuroscience Unit, Okinawa Institute of Science and Technology Graduate University, Onna, Okinawa 904 0495, Japan
| | - E De Schutter
- Computational Neuroscience Unit, Okinawa Institute of Science and Technology Graduate University, Onna, Okinawa 904 0495, Japan
| |
Collapse
|
7
|
Drawert B, Hellander A, Bales B, Banerjee D, Bellesia G, Daigle BJ, Douglas G, Gu M, Gupta A, Hellander S, Horuk C, Nath D, Takkar A, Wu S, Lötstedt P, Krintz C, Petzold LR. Stochastic Simulation Service: Bridging the Gap between the Computational Expert and the Biologist. PLoS Comput Biol 2016; 12:e1005220. [PMID: 27930676 PMCID: PMC5145134 DOI: 10.1371/journal.pcbi.1005220] [Citation(s) in RCA: 46] [Impact Index Per Article: 5.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/11/2016] [Accepted: 10/24/2016] [Indexed: 01/25/2023] Open
Abstract
We present StochSS: Stochastic Simulation as a Service, an integrated development environment for modeling and simulation of both deterministic and discrete stochastic biochemical systems in up to three dimensions. An easy to use graphical user interface enables researchers to quickly develop and simulate a biological model on a desktop or laptop, which can then be expanded to incorporate increasing levels of complexity. StochSS features state-of-the-art simulation engines. As the demand for computational power increases, StochSS can seamlessly scale computing resources in the cloud. In addition, StochSS can be deployed as a multi-user software environment where collaborators share computational resources and exchange models via a public model repository. We demonstrate the capabilities and ease of use of StochSS with an example of model development and simulation at increasing levels of complexity.
Collapse
Affiliation(s)
- Brian Drawert
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
- * E-mail:
| | - Andreas Hellander
- Department of Information Technology, Division of Scientific Computing, Uppsala University, Uppsala, Sweden
| | - Ben Bales
- Department of Mechanical Engineering, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Debjani Banerjee
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Giovanni Bellesia
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Bernie J. Daigle
- Departments of Biological Sciences and Computer Science, The University of Memphis, Memphis, Tennessee, United States of America
| | - Geoffrey Douglas
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Mengyuan Gu
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Anand Gupta
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Stefan Hellander
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Chris Horuk
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Dibyendu Nath
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Aviral Takkar
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Sheng Wu
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Per Lötstedt
- Department of Information Technology, Division of Scientific Computing, Uppsala University, Uppsala, Sweden
| | - Chandra Krintz
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Linda R. Petzold
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
- Department of Mechanical Engineering, University of California, Santa Barbara, Santa Barbara, California, United States of America
| |
Collapse
|
8
|
Drawert B, Hellander A, Bales B, Banerjee D, Bellesia G, Daigle BJ, Douglas G, Gu M, Gupta A, Hellander S, Horuk C, Nath D, Takkar A, Wu S, Lötstedt P, Krintz C, Petzold LR. Stochastic Simulation Service: Bridging the Gap between the Computational Expert and the Biologist. PLoS Comput Biol 2016. [PMID: 27930676 DOI: 10.1371/journal.pcbi] [Citation(s) in RCA: 21] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 05/11/2023] Open
Abstract
We present StochSS: Stochastic Simulation as a Service, an integrated development environment for modeling and simulation of both deterministic and discrete stochastic biochemical systems in up to three dimensions. An easy to use graphical user interface enables researchers to quickly develop and simulate a biological model on a desktop or laptop, which can then be expanded to incorporate increasing levels of complexity. StochSS features state-of-the-art simulation engines. As the demand for computational power increases, StochSS can seamlessly scale computing resources in the cloud. In addition, StochSS can be deployed as a multi-user software environment where collaborators share computational resources and exchange models via a public model repository. We demonstrate the capabilities and ease of use of StochSS with an example of model development and simulation at increasing levels of complexity.
Collapse
Affiliation(s)
- Brian Drawert
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Andreas Hellander
- Department of Information Technology, Division of Scientific Computing, Uppsala University, Uppsala, Sweden
| | - Ben Bales
- Department of Mechanical Engineering, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Debjani Banerjee
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Giovanni Bellesia
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Bernie J Daigle
- Departments of Biological Sciences and Computer Science, The University of Memphis, Memphis, Tennessee, United States of America
| | - Geoffrey Douglas
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Mengyuan Gu
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Anand Gupta
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Stefan Hellander
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Chris Horuk
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Dibyendu Nath
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Aviral Takkar
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Sheng Wu
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Per Lötstedt
- Department of Information Technology, Division of Scientific Computing, Uppsala University, Uppsala, Sweden
| | - Chandra Krintz
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
| | - Linda R Petzold
- Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California, United States of America
- Department of Mechanical Engineering, University of California, Santa Barbara, Santa Barbara, California, United States of America
| |
Collapse
|
9
|
Strehl R, Ilie S. Hybrid stochastic simulation of reaction-diffusion systems with slow and fast dynamics. J Chem Phys 2015; 143:234108. [DOI: 10.1063/1.4937491] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/14/2022] Open
Affiliation(s)
- Robert Strehl
- Department of Mathematics, Ryerson University, Toronto, Ontario M5B 2K3, Canada
| | - Silvana Ilie
- Department of Mathematics, Ryerson University, Toronto, Ontario M5B 2K3, Canada
| |
Collapse
|