Premium
Molecular distance geometry methods: from continuous to discrete
Author(s) -
Liberti Leo,
Lavor Carlile,
Mucherino Antonio,
Maculan Nelson
Publication year - 2011
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00757.x
Subject(s) - euclidean space , euclidean geometry , euclidean distance , geometry , discrete geometry , context (archaeology) , distance , weighted voronoi diagram , graph , topology (electrical circuits) , computer science , mathematics , combinatorics , voronoi diagram , paleontology , shortest path problem , biology
Distance geometry problems (DGP) arise from the need to position entities in the Euclidean K ‐space given some of their respective distances. Entities may be atoms (molecular distance geometry), wireless sensors (sensor network localization), or abstract vertices of a graph (graph drawing). In the context of molecular distance geometry, the distances are usually known because of chemical properties and nuclear magnetic resonance experiments; sensor networks can estimate their relative distance by recording the power loss during a two‐way exchange; finally, when drawing graphs in two or three dimensions, the graph to be drawn is given, and therefore distances between vertices can be computed. DGPs involve a search in a continuous Euclidean space, but sometimes the problem structure helps reduce the search to a discrete set of points. In this paper we survey some continuous and discrete methods for solving some problems of molecular distance geometry.