Chapter
Automatic Inference of Graph Transformation Rules Using the Cyclic Nature of Chemical Reactions
Affiliations
Organisations
- (1) University of Vienna, grid.10420.37
- (2) University of Southern Denmark, grid.10825.3e, SDU
- (3) Fraunhofer Institute for Cell Therapy and Immunology, grid.418008.5
- (4) Leipzig University, grid.9647.c
- (5) Max Planck Institute for Mathematics in the Sciences, grid.419532.8
- (6) Santa Fe Institute, grid.209665.e
- (7) University of Copenhagen, grid.5254.6, KU
Description
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.