title: A Branch-and-Bound Approach for Tautomer Enumeration.
abstract: Knowledge about tautomer forms of a structure is important since, e.g., a property prediction for a molecule can yield to different results which depend on the individual tautomer. Tautomers are isomers that can be transformed to each other through chemical equilibrium reactions. In this paper the first exact Branch-and-Bound (B&B) algorithm to calculate tautomer structures is proposed. The algorithm is complete in the sense of tautomerism and generates all possible tautomers of a structure according to the tautomer definition, it is initialized with. To be efficient, the algorithm takes advantage of symmetric and formation properties. Some restrictions are used to enable an early pruning of some branches of the B&B tree. This is important, since a simple enumeration strategy would lead to number of candidate tautomers that is exponentially increasing with the number of hydrogen atoms and their attachment sites. The proposed implementation of the B&B algorithm covers the majority of the prototropic tautomer cases, but can be adapted to other kinds of tautomerism too. Furthermore, a computer processable definition of tautomerism is given in the form of the moving hydrogen atom problem.
authors.affiliation: Leibniz Institute for Age Research - Fritz Lipmann Institute, Beutenbergstr. 11, 07745 Jena, Germany phone: +49-3641-65-6205. thalheim@fli-leibniz.de.|UFZ Department of Ecological Chemistry, Helmholtz Centre for Environmental Research, Permoserstrasse 15, 04318 Leipzig, Germany. thalheim@fli-leibniz.de.|Institute for Organic Chemistry, Technical University Bergakademie Freiberg, Leipziger Strasse 29, 09596 Freiberg, Germany. thalheim@fli-leibniz.de.
authors.forename: Torsten
authors.initials: T
authors.lastname: Thalheim
authors.affiliation: UFZ Department of Ecological Chemistry, Helmholtz Centre for Environmental Research, Permoserstrasse 15, 04318 Leipzig, Germany.
authors.forename: Barbara
authors.initials: B
authors.lastname: Wagner
authors.affiliation: UFZ Department of Ecological Chemistry, Helmholtz Centre for Environmental Research, Permoserstrasse 15, 04318 Leipzig, Germany.
authors.forename: Ralph
authors.initials: R
authors.lastname: Kühne
authors.affiliation: Parallel Computing and Complex Systems Group, Department of Computer Science, University of Leipzig, Augustusplatz 10, 04109 Leipzig, Germany.
authors.forename: Martin
authors.initials: M
authors.lastname: Middendorf
authors.affiliation: UFZ Department of Ecological Chemistry, Helmholtz Centre for Environmental Research, Permoserstrasse 15, 04318 Leipzig, Germany.|Institute for Organic Chemistry, Technical University Bergakademie Freiberg, Leipziger Strasse 29, 09596 Freiberg, Germany.
authors.forename: Gerrit
authors.initials: G
authors.lastname: Schüürmann
mesh_terms: D000465:Algorithms; D007536:Isomerism; D008958:Models, Molecular; D012984:Software
keywords: Branch-and-Bound; Chemoinformatics; Combinatorial chemistry; Combinatorial optimization; Computational chemistry; Double bond; Exact algorithm; Hydrogen atom shift; Moving hydrogen atom; Optimization problem; Proton-shift tautomerism; Tautomerism