Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/74922
Type: Artigo de periódico
Title: The discretizable distance geometry problem
Author: Mucherino, A
Lavor, C
Liberti, L
Abstract: We introduce the discretizable distance geometry problem in R-3 (DDGP(3)), which consists in a subclass of instances of the Distance Geometry Problem for which an embedding in R-3 can be found by means of a discrete search. We show that the DDGP(3) is a generalization of the discretizable molecular distance geometry problem (DMDGP), and we discuss the main differences between the two problems. We prove that the DDGP(3) is NP-hard and we extend the Branch & Prune (BP) algorithm, previously used for the DMDGP, for solving instances of the DDGP(3). Protein graphs may or may not be in DMDGP and/or DDGP3 depending on vertex orders and edge density. We show experimentally that as distance thresholds decrease, PDB protein graphs which fail to be in the DMDGP still belong to DDGP(3), which means that they can still be solved using a discrete search.
Subject: Distance geometry
DDGP(3)
DMDGP
Combinatorial reformulations
Branch and prune
Country: Alemanha
Editor: Springer Heidelberg
Rights: fechado
Identifier DOI: 10.1007/s11590-011-0358-3
Date Issue: 2012
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000315348000008.pdf383.79 kBAdobe PDFView/Open


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