Flamm, ChristophChristophFlammMerkle, DanielDanielMerkleStadler, Peter F.Peter F.StadlerThorsen, UffeUffeThorsen2022-03-132022-03-132016https://publica.fraunhofer.de/handle/publica/39260010.1007/978-3-319-40530-8_13Graph 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 problemenchemistryatom-atom mappingmaximum common edge subgraphinteger linear programmingnetwork completion610620conference paper