Abstract
We develop a new ‘thermodynamic’ approach to stochastic graph-rewriting. The ingredients are a finite set of reversible graph-rewriting rules \({\mathcal{G}}\) (called generating rules), a finite set of connected graphs \({\mathcal{P}}\) (called energy patterns), and an energy cost function \(\epsilon:{\mathcal{P}}\to{\mathbb{R}}\). The idea is that \({\mathcal{G}}\) defines the qualitative dynamics by showing which transformations are possible, while \({\mathcal{P}}\) and ε specify the long-term probability π of any graph reachable under \({\mathcal{G}}\). Given \({\mathcal{G}}, {\mathcal{P}}\), we construct a finite set of rules \({\mathcal{G}}_{\mathcal{P}}\) which (i) has the same qualitative transition system as \({\mathcal{G}}\), and (ii) when equipped with suitable rates, defines a continuous-time Markov chain of which π is the unique fixed point. The construction relies on the use of site graphs and a technique of ‘growth policy’ for quantitative rule refinement which is of independent interest. The ‘division of labour’ between the qualitative and the long-term quantitative aspects of the dynamics leads to intuitive and concise descriptions for realistic models (see the example in §4). It also guarantees thermodynamical consistency (aka detailed balance), otherwise known to be undecidable, which is important for some applications. Finally, it leads to parsimonious parameterizations of models, again an important point in some applications.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bachman, J.A., Sorger, P.: New approaches to modeling complex biochemistry. Nature Methods 8(2), 130 (2011)
Bai, F., Branch, R.W., Nicolau Jr., D.V., Pilizota, T., Steel, B.C., Maini, P.K., Berry, R.M.: Conformational spread as a mechanism for cooperativity in the bacterial flagellar switch. Science 327(5966), 685–689 (2010)
Bournez, O., Côme, G.-M., Conraud, V., Kirchner, H., Ibanescu, L.: A rule-based approach for automated generation of kinetic chemical mechanisms. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 30–45. Springer, Heidelberg (2003)
Danos, V., Feret, J., Fontana, W., Krivine, J.: Scalable simulation of cellular signaling networks. In: Asian Symposium on Programming Languages and Systems, pp. 139–157 (2007)
Danos, V., Harmer, R., Winskel, G.: Constraining rule-based dynamics with types. Mathematical Structures in Computer Science 23(2), 272–289 (2013)
Danos, V., Oury, N.: Equilibrium and termination II: the case of Petri Nets. Mathematical Structures in Computer Science 23(2), 290–307 (2013)
Danos, V.: Agile modelling of cellular signalling. SOS 2008 Invited paper, Electronic Notes in Theoretical Computer Science 229(4), 3–10 (2009)
Danos, V., Oury, N.: Equilibrium and termination. In: Barry Cooper, S., Panangaden, P., Kashefi, E. (eds.) Proceedings Sixth Workshop on Developments in Computational Models: Causality, Computation, and Physics. EPTCS, vol. 26, pp. 75–84 (2010)
Diers, Y.: Familles universelles de morphismes. Tech. report, Université des Sciences et Techniques de Lille I (1978)
Dixon, L., Kissinger, A.: Open graphs and monoidal theories. arXiv:1011.4114 (2010)
Ehrig, H.: Handbook of graph grammars and computing by graph transformation: Applications, Languages and Tools, vol. 2. World Scientific Publishing Company (1999)
Faeder, J.R., Blinov, M.L., Hlavacek, W.S.: Rule-based modeling of biochemical systems with BioNetGen. Methods Mol. Biol. 500, 113–167 (2009)
Gross, T., Sayama, H.: Adaptive networks. Springer (2009)
Hayman, J., Heindel, T.: Pattern graphs and rule-based models: The semantics of kappa. In: Pfenning, F. (ed.) FOSSACS 2013. LNCS, vol. 7794, pp. 1–16. Springer, Heidelberg (2013)
Heckel, R.: DPO transformation with open maps. Graph Transformations, 203–217 (2012)
Heckel, R.: Dpo transformation with open maps. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) ICGT 2012. LNCS, vol. 7562, pp. 203–217. Springer, Heidelberg (2012)
Hlavacek, W.S., Faeder, J.R., Blinov, M.L., Posner, R.G., Hucka, M., Fontana, W.: Rules for modeling signal-transduction systems. Science Signalling 2006(344) (2006)
Krivine, J., Milner, R., Troina, A.: Stochastic bigraphs. Electronic Notes in Theoretical Computer Science 218, 73–96 (2008)
Lack, S., Sobociński, P.: Adhesive categories. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol. 2987, pp. 273–288. Springer, Heidelberg (2004)
Lopez, C.F., Muhlich, J.L., Bachman, J.A., Sorger, P.K.: Programming biological models in python using pysb. Molecular Systems Biology 9(1) (2013)
Lynch, J.: A logical characterization of individual-based models. In: Proceedings of Logic in Computer Science, pp. 203–217 (2008)
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E., et al.: Equation of state calculations by fast computing machines. The Journal of Chemical Physics 21(6), 1087 (1953)
Murphy, E., Danos, V., Feret, J., Harmer, R., Krivine, J.: Rule-based modelling and model resolution. In: Lohdi, H., Muggleton, S. (eds.) Elements of Computational Systems Biology. Wiley (2010)
Tiger, C.-F., Krause, F., Cedersund, G., Palmér, R., Klipp, E., Hohmann, S., Kitano, H., Krantz, M.: A framework for mapping, visualisation and automatic model creation of signal-transduction networks. Molecular Systems Biology 8(1) (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Danos, V., Harmer, R., Honorato-Zimmer, R. (2013). Thermodynamic Graph-Rewriting. In: D’Argenio, P.R., Melgratti, H. (eds) CONCUR 2013 – Concurrency Theory. CONCUR 2013. Lecture Notes in Computer Science, vol 8052. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40184-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-40184-8_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40183-1
Online ISBN: 978-3-642-40184-8
eBook Packages: Computer ScienceComputer Science (R0)