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

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 (iDDGP) and introduce two angular Branch-and-Prune (BP) frameworks: the interval Angular Branch-and-Prune (iABP) method and its torsion-guided extension, the interval Torsion-angle Branch-and-Prune (iTBP) method. Both methods transform interval distance information into angular constraints on circular arcs; iABP uses these constraints to reduce explicit feasibility checks during branching, while iTBP 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 iDDGP instances from Protein Data Bank structures. Computational experiments indicate that iABP improves the embedding-normalized feasible-solution yield relative to interval BP (iBP), a standard enumerative BP baseline for iDDGP instances, and that both angular methods find feasible realizations for more instances than iBP. Moreover, iTBP attains the lowest minimum RMSD on all instances for which both angular methods find feasible realizations, highlighting the benefit of incorporating torsion-angle information.