An Angle-Based Algorithmic Framework for the Interval Discretizable Distance Geometry Problem

Abstract

Distance Geometry is central to protein structure determination from Nuclear Magnetic Resonance data, where distance restraints are naturally uncertain. We study the interval Discretizable Distance Geometry Problem (\textit{i}DDGP) and introduce two angular Branch-and-Prune (BP) frameworks: the interval Angular Branch-and-Prune (\textit{i}ABP) method and its torsion-guided extension, the interval Torsion-angle Branch-and-Prune (\textit{i}TBP) method. Both methods transform interval distance information into angular constraints on circular arcs; \textit{i}ABP uses these constraints to reduce explicit feasibility checks during branching, while \textit{i}TBP further incorporates prescribed torsion-angle intervals to encode local chirality and planarity information. We develop the corresponding geometric foundations and describe a systematic construction of biologically meaningful \textit{i}DDGP instances from Protein Data Bank structures. Computational experiments indicate that \textit{i}ABP improves the embedding-normalized feasible-solution yield relative to interval BP (\textit{i}BP), a standard enumerative BP baseline for \textit{i}DDGP instances, and that both angular methods find feasible realizations for more instances than \textit{i}BP. Moreover, \textit{i}TBP attains the lowest minimum RMSD on all instances for which both angular methods find feasible realizations, highlighting the benefit of incorporating torsion-angle information.