Cropped cubes
Jon Lee
J Combin Optim
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.
Jon Lee
J Combin Optim
Pierre Bonami, Lorenz T. Biegler, et al.
Discrete Optimization
Brenda L. Dietrich, Jon Lee, et al.
Annals of Operations Research
Pietro Belotti, Jon Lee, et al.
Optimization Methods and Software