Optimization Online


The iBP algorithm for the discretizable molecular distance geometry problem with interval data

Carlile Lavor(clavor***at***ime.unicamp.br)
Leo Liberti(leoliberti***at***gmail.com)
Antonio Mucherino(mucherino***at***cerfacs.fr)

Abstract: The Distance Geometry Problem in three dimensions consists in finding an embedding in R^3 of a given nonnegatively weighted simple undirected graph such that edge weights are equal to the corresponding Euclidean distances in the embedding. This is a continuous search problem that can be discretized under some assumptions on the minimum degree of the vertices. In this paper we discuss the case where some of the edge weights are subject to uncertainty within a given nonnegative interval. We show that a discretization is still possible and propose the iBP algorithm to solve the problem. The approach is validated by some computational experiments on a set of artificially generated instances.

Keywords: distance geometry, combinatorial reformulation, protein molecules, NMR data, interval branch and prune

Category 1: Applications -- Science and Engineering (Biomedical Applications )

Category 2: Combinatorial Optimization (Other )


Download: [PDF]

Entry Submitted: 01/20/2011
Entry Accepted: 01/20/2011
Entry Last Modified: 01/20/2011

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 Programming Society