Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Automatic inference of graph transformation rules using the cyclic nature of chemical reactions

: Flamm, Christoph; Merkle, Daniel; Stadler, Peter F.; Thorsen, Uffe


Echahed, R.:
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 International Publishing, 2016 (Lecture Notes in Computer Science 9761)
ISBN: 978-3-319-40529-2 (Print)
ISBN: 978-3-319-40530-8 (Online)
International Conference on Graph Transformation (ICGT) <9, 2016, Vienna>
Conference "Software Technologies - Application and Foundations" (STAF) <2016, Vienna>
Conference Paper
Fraunhofer IZI ()
chemistry; atom-atom mapping; maximum common edge subgraph; integer linear programming; network completion

Graph transformation systems have the potential to be realistic models of chemistry, provided a comprehensive collection of reaction rules can be extracted from the body of chemical knowledge. A first key step for rule learning is the computation of atom-atom mappings, i.e., the atom-wise correspondence between products and educts of all published chemical reactions. This can be phrased as a maximum common edge subgraph problem with the constraint that transition states must have cyclic structure. We describe a search tree method well suited for small edit distance and an integer linear program best suited for general instances and demonstrate that it is feasible to compute atom-atom maps at large scales using a manually curated database of biochemical reactions as an example. In this context we address the network completion problem