The Propagation Approach for Computing Biochemical Reaction Networks
Pages 310 - 322
Abstract
We introduce propagation models (PMs), a formalism able to express several kinds of equations that describe the behavior of biochemical reaction networks. Furthermore, we introduce the propagation abstract data type (PADT), which separates concerns regarding different numerical algorithms for the transient analysis of biochemical reaction networks from concerns regarding their implementation, thus allowing for portable and efficient solutions. The state of a propagation abstract data type is given by a vector that assigns mass values to a set of nodes, and its $({\bf next})$ operator propagates mass values through this set of nodes. We propose an approximate implementation of the $({\bf next})$ operator, based on threshold abstraction, which propagates only "significant" mass values and thus achieves a compromise between efficiency and accuracy. Finally, we give three use cases for propagation models: the chemical master equation (CME), the reaction rate equation (RRE), and a hybrid method that combines these two equations. These three applications use propagation models in order to propagate probabilities and/or expected values and variances of the model's variables.
References
[1]
S.B. Akers, "Binary Decision Diagrams," IEEE Trans. Computers, vol. C-27, no. 6, pp. 509-516, June 1978.
[2]
K. Ball, T.G. Kurtz, L. Popovic, and G. Rempala, "Asymptotic Analysis of Multiscale Approximations to Reaction Networks," The Annals of Applied Probability, vol. 16, no. 4, pp. 1925-1961, 2006.
[3]
K. Chatterjee and T.A. Henzinger, "Value Iteration," 25 Years of Model Checking, O. Grumberg and H. Veith, eds., vol. 5000, pp. 107-138, Springer, 2008.
[4]
P. Deuflhard, W. Huisinga, T. Jahnke, and M. Wulkow, "Adaptive Discrete Galerkin Methods Applied to the Chemical Master Equation," SIAM J. Scientific Computing, vol. 30, no. 6, pp. 2990- 3011, 2008.
[5]
F. Didier, T.A. Henzinger, M. Mateescu, and V. Wolf, "Approximation of Event Probabilities in Noisy Cellular Processes," Proc. Seventh Int'l Conf. Computational Methods in Systems Biology (CMSB), vol. 5688, pp. 173-188, 2009.
[6]
F. Didier, T.A. Henzinger, M. Mateescu, and V. Wolf, "Fast Adaptive Uniformization of the Chemical Master Equation," Proc. Int'l Workshop High Performance Computational Systems Biology (HIBI '09), pp. 118-127, 2009.
[7]
F. Didier, T.A. Henzinger, M. Mateescu, and V. Wolf, "SABRE: A Tool for Stochastic Analysis of Biochemical Reaction Networks," Proc. Seventh Int'l Conf. Quantitative Evaluation of Systems (QEST), pp. 193-194, 2010.
[8]
S. Engblom, "Computing the Moments of High Dimensional Solutions of the Master Equation," Applied Math. Computation, vol. 180, pp. 498-515, 2006.
[9]
S. Engblom, "Galerkin Spectral Method Applied to the Chemical Master Equation," Comm. Computational Physics, vol. 5, pp. 871- 896, 2009.
[10]
B.L. Fox and P.W. Glynn, "Computing Poisson Probabilities," Comm. ACM, vol. 31, no. 4, pp. 440-445, 1988.
[11]
D.T. Gillespie, "A Rigorous Derivation of the Chemical Master Equation," Physica A, vol. 188, pp. 404-425, 1992.
[12]
D.T. Gillespie, "Simulation Methods in Systems Biology," Formal Methods for Computational Systems Biology, vol. 5016, pp. 125-167, 2008.
[13]
A. Hellander, "Efficient Computation of Transient Solutions of the Chemical Master Equation Based on Uniformization and Quasi-Monte Carlo," J. Chemical Physics, vol. 128, no. 15, p. 154109, 2008.
[14]
A. Hellander and P. Lötstedt, "Hybrid Method for the Chemical Master Equation," J. Computational Physics, vol. 227, pp. 100-122, 2007.
[15]
T.A. Henzinger, B. Jobstmann, and V. Wolf, "Formalisms for Specifying Markovian Population Models," Proc. Third Int'l Workshop Reachability Problems, pp. 3-23, 2009.
[16]
T.A. Henzinger and M. Mateescu, "Propagation Models for Computing Biochemical Reaction Networks," Proc. Ninth Int'l Conf. Computational Methods in Systems Biology, pp. 1-3, 2011.
[17]
T.A. Henzinger, L. Mikeev, M. Mateescu, and V. Wolf, "Hybrid Numerical Solution of the Chemical Master Equation," Proc. Eighth Int'l Conf. Computational Methods in Systems Biology, pp. 55- 65, 2010.
[18]
A. Jensen, "Markoff Chains as an Aid in the Study of Markoff Processes," Skandinavisk Aktuarietidskrift, vol. 36, pp. 87-91, 1953.
[19]
N.G.v. Kampen, Stochastic Processes in Physics and Chemistry, third ed. Elsevier, 2007.
[20]
T. Kurtz, Approximation of Population Processes. Soc. for Industrial Math., 1981.
[21]
B. Liskov and S.N. Zilles, "Programming with Abstract Data Types," SIGPLAN Notices, vol. 9, no. 4, pp. 50-59, 1974.
[22]
M. Mateescu, "Propagation Models for Biochemical Reaction Networks," PhD thesis, EPFL, 2011.
[23]
H.H. McAdams and A. Arkin, "It's a Noisy Business!" Trends in Genetics, vol. 15, no. 2, pp. 65-69, 1999.
[24]
B. Munsky and M. Khammash, "The Finite State Projection Algorithm for the Solution of the Chemical Master Equation," J. Chemical Physics, vol. 124, p. 044144, 2006.
[25]
P. Quaglia, "Computational Methods in Systems Biology," Proc. Eighth Int'l Conf. Computational Methods in Systems Biology (CMSB '10), 2010.
[26]
A. Reibman and K. Trivedi, "Numerical Transient Analysis of Markov Models," Computers and Operations Research, vol. 15, no. 1, pp. 19-36, 1988.
[27]
W. Sandmann and V. Wolf, "A Computational Stochastic Modeling Formalism for Biological Networks," Enformatika Trans. Eng., Computing and Technology, vol. 14, pp. 132-137, 2006.
[28]
R. Sidje, K. Burrage, and S. MacNamara, "Inexact Uniformization Method for Computing Transient Distributions of Markov Chains," SIAM J. Scientific Computing, vol. 29, no. 6, pp. 2562- 2580, 2007.
[29]
W.J. Stewart, Introduction to the Numerical Solution of Markov Chains. Princeton Univ. Press, 1995.
[30]
C. Strelen, "Approximate Disaggregation-Aggregation Solutions for General Queueing Networks," Soc. for Computer Simulation, pp. 773-778, 1997.
[31]
P.S. Swain, M.B. Elowitz, and E.D. Siggia, "Intrinsic and Extrinsic Contributions to Stochasticity in Gene Expression," Proc. Nat'l Academy of Sciences USA, vol. 99, no. 20, pp. 12795-12800, 2002.
[32]
A. van Moorsel and W. Sanders, "Adaptive Uniformization," ORSA Comm. in Statistics: Stochastic Models, vol. 10, no. 3, pp. 619- 648, 1994.
[33]
J. Zhang, L.T. Watson, and Y. Cao, "A Modified Uniformization Method for the Solution of the Chemical Master Equation," Computers and Math. with Applications, vol. 59, no. 1, pp. 573-584, 2010.
Recommendations
Symmetric Fast Marching Schemes for Better Numerical Isotropy
Existing fast marching methods solve the Eikonal equation using a continuous (first-order) model to estimate the accumulated cost, but a discontinuous (zero-order) model for the traveling cost at each grid point. As a result the estimate of the ...
A Hybrid Cellular Automaton Model of Solid Tumor Growth and Bioreductive Drug Transport
Bioreductive drugs are a class of hypoxia selective drugs that are designed to eradicate the hypoxic fraction of solid tumors. Their activity depends upon a number of biological and pharmacological factors and we used a mathematical modeling approach to ...
Keynote on "the propagation approach for computing biochemical reaction networks"
WSC '12: Proceedings of the Winter Simulation ConferenceJoint work with Maria Mateescu.
Propagation models provide a framework for describing algorithms for the transient analysis of stochastic state transition systems, such as computing event probabilities, expectancies, and variances on biochemical ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 March 2013
Published in TCBB Volume 10, Issue 2
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 88Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in