The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances

Carlile Lavor (), Leo Liberti () and Antonio Mucherino ()

Journal of Global Optimization, 2013, vol. 56, issue 3, 855-871

Abstract: The Distance Geometry Problem in three dimensions consists in finding an embedding in $${\mathbb{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 we consider the full-atom representation of the protein backbone and 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. Copyright Springer Science+Business Media, LLC. 2013

Keywords: Distance geometry; Protein conformations; NMR data; Combinatorial optimization; Interval Branch and Prune (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-011-9799-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:56:y:2013:i:3:p:855-871

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-011-9799-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().