The Branch and Prune Algorithm for the Molecular Distance Geometry Problem with Inexact Distances
A. Mucherino, C. Lavor

We consider the Discretizable Molecular Distance Geometry Problem (DMDGP), which consists in a subclass of distance geometry instances (related to molecules) that can be solved by combinatorial optimization. We present a modified version of the Branch and Prune (BP) algorithm, previously proposed for solving these instances, in which exact distances are not known, but rather intervals where the actual distances are contained. This assumption is realistic, because instances of this problem can be defined by applying experimental techniques, such as the Nuclear Magnetic Resonance (NMR), that are subject to errors. Computational experiences show how inaccurate data can affect the quality and the number of solutions which are found by the BP algorithm. Depending on the errors introduced in the data, less accurate solutions or a larger number of solutions is found. In the latter case, clusters containing the most similar conformations can be identified, and the cardinality of the solution set can be reduced.