A Computational Stochastic Modeling Formalism for Biological Networks

Authors: Werner Sandmann, Verena Wolf

Abstract:

Stochastic models of biological networks are well established in systems biology, where the computational treatment of such models is often focused on the solution of the so-called chemical master equation via stochastic simulation algorithms. In contrast to this, the development of storage-efficient model representations that are directly suitable for computer implementation has received significantly less attention. Instead, a model is usually described in terms of a stochastic process or a "higher-level paradigm" with graphical representation such as e.g. a stochastic Petri net. A serious problem then arises due to the exponential growth of the model-s state space which is in fact a main reason for the popularity of stochastic simulation since simulation suffers less from the state space explosion than non-simulative numerical solution techniques. In this paper we present transition class models for the representation of biological network models, a compact mathematical formalism that circumvents state space explosion. Transition class models can also serve as an interface between different higher level modeling paradigms, stochastic processes and the implementation coded in a programming language. Besides, the compact model representation provides the opportunity to apply non-simulative solution techniques thereby preserving the possible use of stochastic simulation. Illustrative examples of transition class representations are given for an enzyme-catalyzed substrate conversion and a part of the bacteriophage λ lysis/lysogeny pathway.

Keywords: Computational Modeling, Biological Networks, Stochastic Models, Markov Chains, Transition Class Models.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060838

References:

[1] A. Arkin, J. Ross, and H. H. McAdams, "Stochastic Kinetic Analysis of Developmental Pathway Bifurcation in Phage λ-Infected Escherichia coli Cells," Genetics, vol. 149, pp. 1633-1648, 1998.
[2] J. M. Bower and H. Bolouri (eds.), Computational Modeling of Genetic and Biochemical Networks. Cambridge, MA: The MIT Press, 2001.
[3] P. Bremaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Berlin-Heidelberg-New York-Tokyo: Springer-Verlag, 1999.
[4] H. Busch, W. Sandmann, and V. Wolf, "A Numerical Aggregation Algorithm for the Enzyme-catalyzed Substrate Conversion," in Proc. Int. Conf. on Computational Methods in Systems Biology (CMSB), Trento, Italy, 18-19 October, to appear, 2006.
[5] Y. Cao, D. T. Gillespie and L. R. Petzold, "Accelerated Stochastic Simulation of the Stiff Enzyme-Substrate Reaction," J. Chemical Physics, vol. 123, no. 14, 2005.
[6] D. R. Cox and H. D. Miller, The Theory of Stochastic Processes. London: Chapman and Hall, 1965.
[7] C. W. Gardiner, Handbook of Stochastic Methods for Physics, Chemistry and the Natural Sciences. Berlin-Heidelberg-New York-Tokyo: Springer-Verlag, 3rd ed., 2004.
[8] D. T. Gillespie, "Exact Stochastic Simulation of Coupled Chemical Reactions," J. Physical Chemistry, vol. 81, no. 25, pp. 2340-2361, 1977.
[9] D. T. Gillespie, "A Rigorous Derivation of the Chemical Master Equation," Physica A, vol. 188, pp. 404-425, 1992.
[10] J. M. Hammersley and D. C. Handscomb, Monte Carlo Methods. London: Methuen, 1964.
[11] J. Hasty, J. Pradines, M. Dolnik, and J. J. Collins, Noise-based switches and amplifiers for gene expression. Proc. Natl. Acad. Sci. USA, vol. 97, no. 5, pp. 2075-80, 2000.
[12] B. H. Junker, D. Kosch¨utzki and F. Schreiber, "Kinetic Modelling with the Systems Biology Modelling Environment SyBME," J. Integrative Bioinformatics, 0018, 2006. Online Journal: http://journal.imbio.de/index.php?paper id=18
[13] S. Karlin and H. M. Taylor, A First Course in Stochastic Processes. New York: Academic Press, 2nd ed., 1975.
[14] D. A. McQuarrie, "Stochastic Approach to Chemical Kinetics," J. Applied Probability, vol. 4, pp. 413-478, 1967.
[15] H. A. Meyer (ed.), Symposium on Monte Carlo Methods. New York: John Wiley & Sons, 1954.
[16] W. Sandmann, "Importance Sampling for Transition Class Models," in Proc. 3rd Int. Workshop on Rare Event Simulation, Pisa, Italy, 2000.
[17] G. Siersetzki, "Algorithmen zur Erzeugung von U¨ bergangsklassen- Modellen aus erweiterten stochastischen Petrinetzen (in German)," Master-s Thesis, Universit¨at Bonn, Institut f¨ur Informatik, 2000.
[18] W. J. Stewart, Introduction to the Numerical Solution of Markov Chains. Princeton University Press, 1994.
[19] J. C. Strelen, "Generation of Transition Class Models from Formal Queueing Network Descriptions," in Proc. 12th European Simulation Symposium, pp. 525-530, 2000.
[20] N. G. Van Kampen, Stochastic Processes in Physics and Chemistry. North-Holland: Elsevier, 1992.
[21] V. Wolf, "Modelling of Biochemical Reactions by Stochastic Automata Networks," Proc. Workshop on Membrane Computing and Biologically Inspired Process Calculi (MeCBIC), Venice, Italy, July 9, 2006.