A Branch-and-Bound Approach for Tautomer Enumeration

Area of Science:

• Computational Chemistry
• Cheminformatics

Background:

• Tautomer forms significantly impact molecular property predictions.
• Tautomers are isomers interconverting via chemical equilibrium.

Purpose of the Study:

• To develop the first exact Branch-and-Bound (B&B) algorithm for calculating tautomer structures.
• To ensure completeness in generating all possible tautomers based on a given definition.

Main Methods:

• An exact Branch-and-Bound (B&B) algorithm is proposed.
• The algorithm leverages symmetry and formation properties for efficiency.
• Restrictions are applied for early pruning of the B&B tree to manage combinatorial explosion.

Main Results:

• The B&B algorithm generates all possible tautomers.
• Efficiency is achieved by exploiting molecular symmetries and properties.
• The method effectively addresses the exponential increase in candidate tautomers.

Conclusions:

• The developed B&B algorithm provides a complete and efficient solution for tautomer enumeration.
• The implementation covers most prototropic tautomer cases and is adaptable to other tautomerism types.
• A computer-processable definition of tautomerism, the moving hydrogen atom problem, is presented.