On a Discretizable Subclass of Instances of the Molecular Distance Geometry Problem
C. Lavor, L. Liberti, A. Mucherino, N. Maculan

The molecular distance geometry problem can be formulated as the problem of finding an immersion in R3 of a given undirected, nonnegatively weighted graph G. In this paper, we discuss a set of graphs G for which the problem may also be formulated as a combinatorial search in discrete space. This is theoretically interesting as an example of “combinatorialization” of a continuous nonlinear problem. It is also algorithmically interesting because the natural combinatorial solution algorithm performs much better than a global optimization approach on the continuous formulation. We present a Branch and Prune algorithm which can be used for obtaining a set of positions of the atoms of protein conformations when only some of the distances between the atoms are known.