Discretization orders for distance geometry problems

作者：Lavor Carlile; Lee Jon; Lee St John Audrey; Liberti Leo^*; Mucherino Antonio; Sviridenko Maxim

来源：Optimization Letters, 2012, 6(4): 783-796.

DOI：10.1007/s11590-011-0302-6

• Molecular distance geometry
• Proteins
• Sensor network localization
• Graph drawing

Given a weighted, undirected simple graph G = (V, E, d) (where d : E -> R+), the distance geometry problem (DGP) is to determine an embedding x : V -> R-K such that for all{i, j} is an element of E parallel to x(i) - x(j)parallel to = d(ij). Although, in general, the DGP is solved using continuous methods, under certain conditions the search is reduced to a discrete set of points. We give one such condition as a particular order on V. We formalize the decision problem of determining whether such an order exists for a given graph and show that this problem is NP-complete in general and polynomial for fixed dimension K. We present results of computational experiments on a set of protein backbones whose natural atomic order does not satisfy the order requirements and compare our approach with some available continuous space searches.

• 出版日期2012-4