Yael Berstein, Jon Lee, et al.
SIAM Journal on Discrete Mathematics
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.
Yael Berstein, Jon Lee, et al.
SIAM Journal on Discrete Mathematics
Jon Lee, Maxim Sviridenko, et al.
Mathematics of Operations Research
Jon Lee
IBM J. Res. Dev
Jon Lee, Maxim Sviridenko, et al.
SIAM Journal on Computing