Authors: Jakob L. Andersen; Christoph Flamm; Daniel Merkle; Peter F. Stadler
Addresses: Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark; Max Planck Institute for Mathematics in the Sciences, Inselstraße 22 D-04103 Leipzig, Germany ' Institute for Theoretical Chemistry, University of Vienna, Währingerstraße 17, A-1090 Wien, Austria ' Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark ' Institute for Theoretical Chemistry, University of Vienna, Währingerstraße 17, A-1090 Wien, Austria Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Härtelstraße 16-18, D-04107, Leipzig, Germany; Max Planck Institute for Mathematics in the Sciences, Inselstraße 22 D-04103 Leipzig, Germany; Fraunhofer Institute for Cell Therapy and Immunology, Perlickstraße 1, D-04103 Leipzig, Germany; Center for non-coding RNA in Technology and Health, University of Copenhagen, Grønnegårdsvej 3, DK-1870 Frederiksberg C, Denmark; Santa Fe Institute, 1399 Hyde Park Rd, Santa Fe, NM 87501, USA
Abstract: The chemical universe of molecules reachable from a set of start compounds by iterative application of a finite number of reactions is usually so vast, that sophisticated and efficient exploration strategies are required to cope with the combinatorial complexity. A stringent analysis of (bio)chemical reaction networks, as approximations of these complex chemical spaces, forms the foundation for the understanding of functional relations in Chemistry and Biology. Graphs and graph rewriting are natural models for molecules and reactions. Borrowing the idea of partial evaluation from functional programming, we introduce partial applications of rewrite rules. A framework for the specification of exploration strategies in graph-rewriting systems is presented. Using key examples of complex reaction networks from carbohydrate chemistry we demonstrate the feasibility of this high-level strategy framework. While being designed for chemical applications, the framework can also be used to emulate higher-level transformation models such as illustrated in a small puzzle game.
Keywords: chemical spaces; generative chemistries; graph grammars; graph transformation; double pushout approach; graph binding; partial rule application; rule composition; borate stabilised formose reaction; partial evaluation; functional programming; rewrite rules; graph rewriting; carbohydrate chemistry.
International Journal of Computational Biology and Drug Design, 2014 Vol.7 No.2/3, pp.225 - 258
Published online: 27 May 2014 *Full-text access for editors Access for subscribers Purchase this article Comment on this article