Abstract
Chemical reaction networks can be automatically generated from graph grammar descriptions, where transformation rules model reaction patterns. Because a molecule graph is connected and reactions in general involve multiple molecules, the transformation must be performed on multisets of graphs. We present a general software package for this type of graph transformation system, which can be used for modelling chemical systems. The package contains a C++ library with algorithms for working with transformation rules in the Double Pushout formalism, e.g., composition of rules and a domain specific language for programming graph language generation. A Python interface makes these features easily accessible. The package also has extensive procedures for automatically visualising not only graphs and transformation rules, but also Double Pushout diagrams and graph languages in form of directed hypergraphs. The software is available as an open source package, and interactive examples can be found on the accompanying webpage.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andersen, J.L., Andersen, T., Flamm, C., Hanczyc, M.M., Merkle, D., Stadler, P.F.: Navigating the chemical space of HCN polymerization and hydrolysis: guiding graph grammars by mass spectrometry data. Entropy 15(10), 4066–4083 (2013)
Andersen, J.L., Flamm, C., Merkle, D., Stadler, P.F.: Inferring chemical reaction patterns using rule composition in graph grammars. J. Syst. Chem. 4(1), 4 (2013)
Andersen, J.L., Flamm, C., Merkle, D., Stadler, P.F.: 50 shades of rule composition. In: Fages, F., Piazza, C. (eds.) FMMB 2014. LNCS, vol. 8738, pp. 117–135. Springer, Heidelberg (2014)
Andersen, J.L., Flamm, C., Merkle, D., Stadler, P.F.: Generic strategies for chemical space exploration. Int. J. Comput. Biol. Drug Des. 7(2/3), 225–258 (2014). TR: http://arxiv.org/abs/1302.4006
Andrei, O., Fernández, M., Kirchner, H., Melançon, G., Namet, O., Pinaud, B.: PORGY: strategy driven interactive transformation of graphs. In: Proceedings of the 6th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2011). Electronic Proceedings in Theoretical Computer Science, vol. 48, pp. 54–68 (2011)
Benkö, G., Flamm, C., Stadler, P.F.: A graph-based toy model of chemistry. J. Chem. Inf. Comput. Sci. 43(4), 1085–1093 (2003)
Braatz, B., Golas, U., Soboll, T.: How to delete categorically - two pushout complement constructions. J. Symb. Comput. 46(3), 246–271 (2011). Applied and Computational Category Theory
Cordella, L., Foggia, P., Sansone, C., Vento, M.: A (sub) graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367 (2004)
Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: An improved algorithm for matching large graphs. In: Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pp. 149–159 (2001)
Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic approaches to graph transformation - Part I: Basic concepts and double pushout approach. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation. Chapter 3, pp. 163–245. World Scientific, Singapore (1997)
Ehrig, K., Heckel, R., Lajios, G.: Molecular analysis of metabolic pathway with graph transformation. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) ICGT 2006. LNCS, vol. 4178, pp. 107–121. Springer, Heidelberg (2006)
Fernández, M., Kirchner, H., Namet, O.: A strategy language for graph rewriting. In: Vidal, G. (ed.) LOPSTR 2011. LNCS, vol. 7225, pp. 173–188. Springer, Heidelberg (2012)
Flamm, C., Ullrich, A., Ekker, H., Mann, M., Högerl, D., Rohrschneider, M., Sauer, S., Scheuermann, G., Klemm, K., Hofacker, I.L., Stadler, P.F.: Evolution of metabolic networks: a computational framework. J. Syst. Chem. 1(4), 4 (2010)
Increpare games: Catalan (2011). http://www.increpare.com/2011/01/catalan/
Gansner, E.R., North, S.C.: An open graph visualization system and its applications to software engineering. Softw. Pract. Exp. 30(11), 1203–1233 (2000)
Himsolt, M.: GML: a portable graph file format. http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/brandenburg/projekte/gml/gml-technical-report.pdf
Kreowski, H.J., Kuske, S.: Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing. Nat. Comput. 10(2), 961–986 (2011)
Mann, M., Ekker, H., Flamm, C.: The graph grammar library - a generic framework for chemical graph rewrite systems. In: Duddy, K., Kappel, G. (eds.) ICMB 2013. LNCS, vol. 7909, pp. 52–53. Springer, Heidelberg (2013)
O’Boyle, N.M., Banck, M., James, C.A., Morley, C., Vandermeersch, T., Hutchison, G.R.: Open Babel: an open chemical toolbox. J. Cheminformatics 3, 33 (2011)
Rosselló, F., Valiente, G.: Analysis of metabolic pathways by graph transformation. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 70–82. Springer, Heidelberg (2004)
Rosselló, F., Valiente, G.: Chemical graphs, chemical reaction graphs, and chemical graph transformation. Electron. Notes Theor. Comput. Sci. 127(1), 157–166 (2005). Proceedings of the International Workshop on Graph-Based Tools (GraBaTs 2004) Graph-Based Tools 2004
Siek, J.G., Lee, L.Q., Lumsdaine, A.: Boost Graph Library: The User Guide and Reference Manual. Pearson Education, Upper Saddle River (2001). http://www.boost.org/libs/graph/
Sylvester, J.J.: On an application of the new atomic theory to the graphical representation of the invari- ants and covariants of binary quantics, with three appendices. Am. J. Math. 1(1), 64–128 (1878)
Taentzer, G.: AGG: A graph transformation environment for modeling and validation of software. In: Pfaltz, J.L., Nagl, M., Böhlen, B. (eds.) AGTIVE 2003. LNCS, vol. 3062, pp. 446–453. Springer, Heidelberg (2004)
Tantau, T.: The TikZ and PGF Packages (2013). http://sourceforge.net/projects/pgf/
Weininger, D.: SMILES, a chemical language and information system. 1. Introduction to methodology and encoding rules. J. Chem. Inf. Comput. Sci. 28(1), 31–36 (1988)
Yadav, M.K., Kelley, B.P., Silverman, S.M.: The potential of a chemical graph transformation system. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 83–95. Springer, Heidelberg (2004)
Acknowledgements
This work is supported by the Danish Council for Independent Research, Natural Sciences, the COST Action CM1304 “Emergence and Evolution of Complex Chemical Systems”, and the ELSI Origins Network (EON), which is supported by a grant from the John Templeton Foundation. The opinions expressed in this publication are those of the authors and do not necessarily reflect the views of the John Templeton Foundation.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
A Examples
A Examples
The following is a short list of examples that show how MedØlDatschgerl can be used via the Python interface. They are all available as modifiable script in the live version of the software, accessible at http://mod.imada.sdu.dk/playground.html.
1.1 A.1 Graph Interface
Graph objects have a full interface to access individual vertices and edges. The labels of vertices and edges can be accessed both in their raw string form, and as their chemical counterpart (if they have one).
1.2 A.2 Graph Morphisms
Graph objects have methods for finding morphisms with the VF2 algorithms for isomorphism and monomorphism. We can therefore easily detect isomorphic graphs, count automorphisms, and search for substructures.
1.3 A.3 Rule Loading
Rules must be specified in GML format.
1.4 A.4 Rule Composition 1 — Unary Operators
Special rules can be constructed from graphs.
1.5 A.5 Rule Composition 2 — Parallel Composition
A pair of rules can be merged to a new rule implementing the parallel transformation.
1.6 A.6 Rule Composition 3 — Supergraph Composition
A pair of rules can (maybe) be composed using a supergraph relation.
1.7 A.7 Reaction Networks 1 — Rule Application
Transformation rules (reaction patterns) can be applied to graphs (molecules) to create new graphs (molecules). The transformations (reactions) implicitly form a directed (multi-)hypergraph (chemical reaction network).
1.8 A.8 Reaction Networks 2 — Repetition
A sub-strategy can be repeated.
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Andersen, J.L., Flamm, C., Merkle, D., Stadler, P.F. (2016). A Software Package for Chemically Inspired Graph Transformation. In: Echahed, R., Minas, M. (eds) Graph Transformation. ICGT 2016. Lecture Notes in Computer Science(), vol 9761. Springer, Cham. https://doi.org/10.1007/978-3-319-40530-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-40530-8_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-40529-2
Online ISBN: 978-3-319-40530-8
eBook Packages: Computer ScienceComputer Science (R0)