About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Optimization Letters
Paper
Discretization orders for distance geometry problems
Abstract
Given a weighted, undirected simple graph G = (V, E, d) (where d: E → ℝ +), the distance geometry problem (DGP) is to determine an embedding x: V → ℝ K such that ∀{i, j} ∈ E {double pipe} X i - x j {double pipe} = 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. © 2011 Springer-Verlag.