Optimization Online


New error measures and methods for realizing protein graphs from distance data

Claudia D'Ambrosio(dambrosio***at***lix.polytechnique.fr)
Ky Vu(vukhacky***at***gmail.com)
Carlile Lavor(clavor***at***ime.unicamp.br)
Leo Liberti(liberti***at***lix.polytechnique.fr)
Nelson Maculan(maculan***at***cos.ufrj.br)

Abstract: 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.

Keywords: distance geometry, protein conformation, mathematical programming

Category 1: Global Optimization (Applications )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: in revision

Download: [PDF]

Entry Submitted: 06/15/2016
Entry Accepted: 06/15/2016
Entry Last Modified: 06/15/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society