Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Discretization orders for distance geometry problems
Author: Lavor, C
Lee, J
Lee-St John, A
Liberti, L
Mucherino, A
Sviridenko, M
Abstract: Given a weighted, undirected simple graph G = (V, E, d) (where d : E -> R+), the distance geometry problem (DGP) is to determine an embedding x : V -> R-K such that for all{i, j} is an element of E parallel to x(i) - x(j)parallel to = d(ij). Although, in general, the DGP is solved using continuous methods, under certain conditions the search is reduced to a discrete set of points. We give one such condition as a particular order on V. We formalize the decision problem of determining whether such an order exists for a given graph and show that this problem is NP-complete in general and polynomial for fixed dimension K. We present results of computational experiments on a set of protein backbones whose natural atomic order does not satisfy the order requirements and compare our approach with some available continuous space searches.
Subject: Molecular distance geometry
Sensor network localization
Graph drawing
Country: Alemanha
Editor: Springer Heidelberg
Rights: fechado
Identifier DOI: 10.1007/s11590-011-0302-6
Date Issue: 2012
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000304624000015.pdf236.5 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.