The Discretizable Molecular Distance Geometry Problem seems Easier on Proteins
Leo Liberti, Carlile Lavor, Antonio Mucherino

Distance geometry methods are used to turn a set of interatomic distances given by NMR experiments into a consistent molecular conformation. In a set of papers, we proposed a Branch-and-Prune (BP) algorithm for computing the set X of all incongruent embeddings of a given protein backbone. Although BP has a worst-case exponential running time in general, we always noticed a linear-like behaviour in computational experiments. In this paper we provide a theoretical explanation to our observations. We show that the BP is fixed-parameter tractable on protein-like graphs, and empirically show that the parameter is constant on a set of proteins from the Protein Data Bank.\\