On a discretizable subclass of instances of the molecular distance geometry problem

The molecular distance geometry problem can be formulated as the problem of finding an immersion in R³ 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.