title: Atom mapping with constraint programming.
abstract: Chemical reactions are rearrangements of chemical bonds. Each atom in an educt molecule thus appears again in a specific position of one of the reaction products. This bijection between educt and product atoms is not reported by chemical reaction databases, however, so that the "Atom Mapping Problem" of finding this bijection is left as an important computational task for many practical applications in computational chemistry and systems biology. Elementary chemical reactions feature a cyclic imaginary transition state (ITS) that imposes additional restrictions on the bijection between educt and product atoms that are not taken into account by previous approaches. We demonstrate that Constraint Programming is well-suited to solving the Atom Mapping Problem in this setting. The performance of our approach is evaluated for a manually curated subset of chemical reactions from the KEGG database featuring various ITS cycle layouts and reaction mechanisms.
authors.affiliation: Bioinformatics Group, Department of Computer Science, University of Freiburg, Georges-Koehler-Allee 106, Freiburg, 79110 Germany.
authors.forename: Martin
authors.initials: M
authors.lastname: Mann
authors.affiliation: Bioinformatics Group, Department of Computer Science, University of Freiburg, Georges-Koehler-Allee 106, Freiburg, 79110 Germany.
authors.forename: Feras
authors.initials: F
authors.lastname: Nahar
authors.affiliation: Bioinformatics Group, Department of Computer Science, University of Freiburg, Georges-Koehler-Allee 106, Freiburg, 79110 Germany.
authors.forename: Norah
authors.initials: N
authors.lastname: Schnorr
authors.affiliation: Bioinformatics Group, Department of Computer Science, University of Freiburg, Georges-Koehler-Allee 106, Freiburg, 79110 Germany ; Centre for Biological Signalling Studies (BIOSS), University of Freiburg, Freiburg, Germany ; Centre for Biological Systems Analysis (ZBSA), Cluster of Excellence, University of Freiburg, Habsburgerstr. 49, Freiburg, 79104 Germany ; Center for non-coding RNA in Technology and Health, University of Copenhagen, Grønnegårdsvej 3, Frederiksberg, 1870 Denmark.
authors.forename: Rolf
authors.initials: R
authors.lastname: Backofen
authors.affiliation: Institute for Theoretical Chemistry, University of Vienna, Währingerstrasse 17, Vienna, 1090 Austria ; Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, University of Leipzig, Härtelstraße 16-18, Leipzig, 04107 Germany ; Max Planck Institute for Mathematics in the Sciences, Inselstraße 22, Leipzig, 04107 Germany ; Fraunhofer Institute for Cell Therapy and Immunology, Perlickstraße 1, Leipzig, 04103 Germany ; Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, 87501 NM USA.
authors.forename: Peter F
authors.initials: PF
authors.lastname: Stadler
authors.affiliation: Institute for Theoretical Chemistry, University of Vienna, Währingerstrasse 17, Vienna, 1090 Austria.
authors.forename: Christoph
authors.initials: C
authors.lastname: Flamm
keywords: Atom-atom mapping; Chemical reaction; Constraint programming; Imaginary transition state