The discretizable distance geometry problem

We introduce the discretizable distance geometry problem in ℝ³ (DDGP₃), which consists in a subclass of instances of the Distance Geometry Problem for which an embedding in ℝ³ can be found by means of a discrete search. We show that the DDGP₃ is a generalization of the discretizable molecular distance geometry problem (DMDGP), and we discuss the main differences between the two problems. We prove that the DDGP₃ is NP-hard and we extend the Branch & Prune (BP) algorithm, previously used for the DMDGP, for solving instances of the DDGP₃. Protein graphs may or may not be in DMDGP and/or DDGP₃ depending on vertex orders and edge density. We show experimentally that as distance thresholds decrease, PDB protein graphs which fail to be in the DMDGP still belong to DDGP₃, which means that they can still be solved using a discrete search.