 Undirected labeled graphs and graph rewriting are natural models of chemical compounds and chemical reactions. This provides a basis for exploring spaces of molecules and computing reaction networks implicitly defined by graph grammars. Molecule graphs are connected, meaning that rewriting steps in general are many-to-many graph transformations. Chemical grammars are typically subject to combinatorial explosion, however, making it often infeasible to compute the underlying network by direct breadth-first expansion. To alleviate this problem, we introduce here partial applications of rules as a basis for the efficient implementation of strategies that are not only well suited for exploration of chemistries defined by graph grammars, but that are also applicable in a generalgraph rewriting context as well. As showcases, we explore a complex chemistry based on the Diels-Alder reaction to explore specific subspaces of the molecular space. As a non-chemical application we use the framework of exploration strategies to model an abstract graph rewriting problem to construct high-level transformations that cannot be directly represented by the Double-Pushout formalism starting from simple DPO transformation rules .
Computational approaches to exploring "chemical universes", i.e., very large sets, potentially infinite sets of compounds that can be constructed by a prescribed collection of reaction mechanisms, in practice suffer from a combinatorial explosion. It quickly becomes impossible to test, for all pairs of compounds in a rapidly growing network, whether they can react with each other. More sophisticated and efficient strategies are therefore required to construct very large chemical reaction networks. Undirected labeled graphs and graph rewriting are natural models of chemical compounds and chemical reactions. Borrowing the idea of partial evaluation from functional programming, we introduce partial applications of rewrite rules. Binding substrate to rules increases the number of rules but drastically prunes the substrate sets to which it might match, resulting in dramatically reduced resource requirements. At the same time, exploration strategies can be guided, e.g. based on restrictions on the product molecules to avoid the explicit enumeration of very unlikely compounds. To this end we introduce here a generic framework for the specification of exploration strategies in graph-rewriting systems. Using key examples of complex chemical networks from sugar chemistry and the realm of metabolic networks we demonstrate the feasibility of a high-level strategy framework. The ideas presented here can not only be used for a strategy-based chemical space exploration that has close correspondence of experimental results, but are much more general. In particular, the framework can be used to emulate higher-level transformation models such as illustrated in a small puzzle game .
A
Computational approaches to exploring "chemical universes", i.e., very large sets, potentially infinite sets of compounds that can be constructed by a prescribed collection of reaction mechanisms, in practice suffer from a combinatorial explosion. It quickly becomes impossible to test, for all pairs of compounds in a rapidly growing network, whether they can react with each other. More sophisticated and efficient strategies are therefore required to construct very large chemical reaction networks.
R
This provides a basis for exploring spaces of molecules and computing reaction networks implicitly defined by graph grammars. Molecule graphs are connected, meaning that rewriting steps in general are many-to-many graph transformations. Chemical grammars are typically subject to combinatorial explosion, however, making it often infeasible to compute the underlying network by direct breadth-first expansion. To alleviate this problem,
Borrowing the idea of partial evaluation from functional programming, we introduce partial applications of rewrite rules. Binding substrate to rules increases the number of rules but drastically prunes the substrate sets to which it might match, resulting in dramatically reduced resource requirements. At the same time, exploration strategies can be guided, e.g. based on restrictions on the product molecules to avoid the explicit enumeration of very unlikely compounds. To this end
R
partial applications of rules as a basis for the efficient implementation of strategies that are not only well suited for exploration of chemistries defined by graph grammars, but that are also applicable in a generalgraph rewriting context as well. As showcases, we explore a complex chemistry based on the Diels-Alder reaction to explore specific subspaces of the molecular space. As a non-chemical application we use the framework of exploration strategies to model an abstract graph rewriting problem to construct
a generic framework for the specification of exploration strategies in graph-rewriting systems. Using key examples of complex chemical networks from sugar chemistry and the realm of metabolic networks we demonstrate the feasibility of a
R
transformations that cannot be directly represented by the Double-Pushout formalism starting from simple DPO transformation rules
strategy framework. The ideas presented here can not only be used for a strategy-based chemical space exploration that has close correspondence of experimental results, but are much more general. In particular, the framework can be used to emulate higher-level transformation models such as illustrated in a small puzzle game