Optimization Online


Molecular distance geometry methods: from continuous to discrete

Leo Liberti (leoliberti***at***gmail.com)
Carlile Lavor (clavor***at***ime.unicamp.br)
Antonio Mucherino (mucherino***at***lix.polytechnique.fr)
Nelson Maculan (maculan***at***cos.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 )


Download: [PDF]

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

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