A Branch-and-Bound Algorithm for the Molecular Ordered Covering Problem

Abstract

The Discretizable Molecular Distance Geometry Problem (DMDGP) plays a key role in the construction of three-dimensional molecular structures from interatomic distances acquired through nuclear magnetic resonance (NMR) spectroscopy, with the primary objective of validating a sequence of distance constraints related to NMR data. This article addresses the escalating complexity of the DMDGP encountered with larger and more flexible molecules by introducing a novel strategy via the Molecular Ordered Covering Problem, which optimizes the ordering of distance constraints to improve computational efficiency in DMDGP resolution. This approach utilizes a specialized Branch-and-Bound (BB) algorithm, tested on both synthetic and actual protein structures from the protein data bank. Our analysis demonstrates the efficacy of the previously proposed greedy heuristic in managing complex molecular scenarios, highlighting the BB algorithm's utility as a validation mechanism. This research contributes to ongoing efforts in molecular structure analysis, with possible implications for areas such as protein folding, drug design, and molecular modeling.

Keywords: Branch-and-Bound; Discretizable Molecular Distance Geometry Problem; Molecular Ordered Covering Problem; Protein Geometry.