A Computational Stochastic Modeling Formalism for Biological Networks

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.

• Werner Sandmann
• Verena Wolf

• Computational Modeling
• Biological Networks
• Stochastic Models
• Markov Chains
• Transition Class Models.

[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.