On the computation of protein backbones by usingartificial backbones of hydrogens

摘要

NMR experiments provide information from which some of the distancesbetween pairs of hydrogen atoms of a protein molecule can be estimated. Such distances canbe exploited in order to identify the three-dimensional conformation of the molecule: thisproblem is known in the literature as the Molecular Distance Geometry Problem (MDGP). Inthis paper, we show how an artificial backbone of hydrogens can be defined which allows thereformulation of the MDGP as a combinatorial problem. This is done with the aim of solvingthe problem by the Branch and Prune (BP) algorithm, which is able to solve it efficiently.Moreover, we show how the real backbone of a protein conformation can be computed byusing the coordinates of the hydrogens found by the BP algorithm. Formal proofs of thepresented results are provided, as well as computational experiences on a set of instanceswhose size ranges from 60 to 6000 atoms.