Discretization orders for distance geometry problems

Discretization orders for distance geometry problems

0.00 Avg rating0 Votes
Article ID: iaor20123497
Volume: 6
Issue: 4
Start Page Number: 783
End Page Number: 796
Publication Date: Apr 2012
Journal: Optimization Letters
Authors: , , , , ,
Keywords: sets, decision
Abstract:

Given a weighted, undirected simple graph G = (V, E, d) (where d : E + equ1 ), the distance geometry problem (DGP) is to determine an embedding x : V K equ2 such that { i , j } E x i x j = d ij equ3 . 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.

Reviews

Required fields are marked *. Your email address will not be published.