The interval Distance Geometry Problem (iDGP) consists in finding a realization in R^K of a simple undirected graph G=(V,E) with nonnegative intervals assigned to the edges in such a way that, for each edge, the Euclidean distance between the realization of the adjacent vertices is within the edge interval bounds. Our aim is to determine the best formulation-based method for this problem restricted to the application of finding protein conformation given some of the inter-atomic distances. To this end, we introduce (a) a new error measure, which could be described as a "root mean square deviation modulo isomers"; (b) a set of new and existing quadratic and semidefinite programming formulations of this problem; (c) a set of new and existing methods for solving these formulations. We then perform a computational evaluation of all the feasible solver+formulation combinations according to new and existing error measures, finding that the best methodology is a new heuristic method based on multiplicative weights updates.
Citation
in revision
Article
View New error measures and methods for realizing protein graphs from distance data