A Branch-and-Bound Approach for Tautomer Enumeration

作者：Thalheim Torsten^*; Wagner Barbara; Kuehne Ralph; Middendorf Martin; Schueuermann Gerrit

来源：Molecular Informatics, 2015, 34(5): 263-275.

DOI：10.1002/minf.201400128

• Branch-and-Bound
• Combinatorial optimization
• Computational chemistry
• Combinatorial chemistry
• Chemoinformatics
• Double bond
• Exact algorithm
• Hydrogen atom shift
• Moving hydrogen atom
• Proton-shift tautomerism
• Optimization problem
• Tautomerism

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 proper-ties. 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.

• 出版日期2015-5