Carlile Lavor, Antonio Mucherino, Leo Liberti, and Nelson Maculan
View Full Paper
Distance geometry, discrete formulation, NMR data, hydrogens, Branch & Prune
The molecular distance geometry problem (MDGP) is the problem of ﬁnding the conformation of a molecule by exploiting known distances between some pairs of its atoms. Estimates of the distances between the atoms can be obtained through experiments of nuclear magnetic resonance (NMR) spectroscopy. The information on the distances, however, is usually limited, because only distances ˚ between hydrogens and shorter than 6 A are usually available, and this makes the solution of the MDGP quite hard. In this paper, we focus our attention on protein backbones and we present a methodology for computing their full-atom conformations starting from NMR data. This task is performed by solving two MDGPs. First of all, only hydrogens are considered: we deﬁne an artiﬁcial backbone of hydrogens for which particular assumptions needed for the discretization of the problem are satisﬁed. This allows for solving the ﬁrst MDGP with an ad hoc algorithm. Secondly, by exploiting the coordinates of the hydrogens and known bond lengths and bond angles, we compute the coordinates of the other atoms forming the protein backbone by using a polynomial-time algorithm. Computational experiments related to real proteins are presented.