×

A software package for chemically inspired graph transformation. (English) Zbl 1344.68105

Echahed, Rachid (ed.) et al., Graph transformation. 9th international conference, ICGT 2016, in memory of Hartmut Ehrig, held as part of STAF 2016, Vienna, Austria, July 5–6, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-40529-2/pbk; 978-3-319-40530-8/ebook). Lecture Notes in Computer Science 9761, 73-88 (2016).
Summary: 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.
For the entire collection see [Zbl 1339.68007].

MSC:

68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
92E20 Classical flows, reactions, etc. in chemistry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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) · Zbl 1341.82105 · doi:10.3390/e15104066
[2] 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) · doi:10.1186/1759-2208-4-4
[3] 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) · Zbl 1402.92166 · doi:10.1007/978-3-319-10398-3_9
[4] 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
[5] 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) · doi:10.4204/EPTCS.48.7
[6] Benkö, G., Flamm, C., Stadler, P.F.: A graph-based toy model of chemistry. J. Chem. Inf. Comput. Sci. 43(4), 1085–1093 (2003) · doi:10.1021/ci0200570
[7] 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 · Zbl 1215.18002 · doi:10.1016/j.jsc.2010.09.007
[8] 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) · Zbl 05112469 · doi:10.1109/TPAMI.2004.75
[9] 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)
[10] 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) · doi:10.1142/9789812384720_0003
[11] 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) · Zbl 1156.92316 · doi:10.1007/11841883_9
[12] 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) · Zbl 1239.68008 · doi:10.1007/978-3-642-29344-3
[13] 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) · doi:10.1186/1759-2208-1-4
[14] Increpare games: Catalan (2011). http://www.increpare.com/2011/01/catalan/
[15] 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) · Zbl 1147.68782 · doi:10.1002/1097-024X(200009)30:11<1203::AID-SPE338>3.0.CO;2-N
[16] Himsolt, M.: GML: a portable graph file format. http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/brandenburg/projekte/gml/gml-technical-report.pdf
[17] 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) · Zbl 1217.68162 · doi:10.1007/s11047-010-9245-6
[18] 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) · Zbl 06279271 · doi:10.1007/978-3-642-38883-5_5
[19] 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) · doi:10.1186/1758-2946-3-33
[20] 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) · Zbl 1116.92312 · doi:10.1007/978-3-540-30203-2_7
[21] 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 · doi:10.1016/j.entcs.2004.12.033
[22] 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/
[23] 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) · doi:10.2307/2369436
[24] 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) · doi:10.1007/978-3-540-25959-6_35
[25] Tantau, T.: The TikZ and PGF Packages (2013). http://sourceforge.net/projects/pgf/
[26] 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) · doi:10.1021/ci00057a005
[27] 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) · Zbl 1116.92326 · doi:10.1007/978-3-540-30203-2_8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.