Molecular distance geometry methods: from continuous to discrete

Leo Liberti (leolibertigmail.com)
Carlile Lavor (clavorime.unicamp.br)
Antonio Mucherino (mucherinolix.polytechnique.fr)
Nelson Maculan (maculancos.ufrj.br)

Abstract: Distance geometry problems 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 2D or 3D, the graph to be drawn is given, and therefore distances between vertices can be computed. Distance geometry problems involve a search in continuous Euclidean space, but sometimes the problem structure helps reduce the search to a discrete set of points. In this paper we survey both continuous and discrete methods for solving some problems of molecular distance geometry.

Keywords: distance geometry, rigidity, network localization, branch-and-prune

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

Category 2: Combinatorial Optimization (Other )

Citation:

Download: [PDF]

Entry Submitted: 09/27/2009
Entry Accepted: 09/27/2009
Entry Last Modified: 10/03/2009

Modify/Update this entry