Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/87349
Type: Artigo
Title: An adaptive branching scheme for the Branch & Prune algorithm applied to Distance Geometry
Author: Gonçalves, DouglasMucherino, AntonioLavor, Carlile
Abstract: The Molecular Distance Geometry Problem (MDGP) is the one of finding molecular conformations that satisfy a set of distance constraints obtained through experimental techniques such as Nuclear Magnetic Resonance (NMR). We consider a subclass of MDGP instances that can be discretized, where the search domain has the structure of a tree, which can be explored by using an interval Branch & Prune (iBP) algorithm. When all available distances are exact, all candidate positions for a given molecular conformation can be enumerated. This is however not possible in presence of interval distances, because a continuous subset of positions can actually be computed for some atoms. The focus of this work is on a new scheme for an adaptive generation of a discrete subset of candidate positions from this continuous subset. Our generated candidate positions do not only satisfy the distances employed in the discretization process, but also additional distances that might be available (the so-called pruning distances). Therefore, this new scheme is able to guide more efficiently the search in the feasible regions of the search domain. In this work, we motivate the development and formally introduce this new adaptive scheme. Presented computational experiments show that iBP, integrated with our new scheme, outperforms the standard iBP on a set of NMR-like instances.
The Molecular Distance Geometry Problem (MDGP) is the one of finding molecular conformations that satisfy a set of distance constraints obtained through experimental techniques such as Nuclear Magnetic Resonance (NMR). We consider a subclass of MDGP instances that can be discretized, where the search domain has the structure of a tree, which can be explored by using an interval Branch & Prune (iBP) algorithm. When all available distances are exact, all candidate positions for a given molecular conformation can be enumerated. This is however not possible in presence of interval distances, because a continuous subset of positions can actually be computed for some atoms. The focus of this work is on a new scheme for an adaptive generation of a discrete subset of candidate positions from this continuous subset. Our generated candidate positions do not only satisfy the distances employed in the discretization process, but also additional distances that might be available (the so-called pruning distances). Therefore, this new scheme is able to guide more efficiently the search in the feasible regions of the search domain. In this work, we motivate the development and formally introduce this new adaptive scheme. Presented computational experiments show that iBP, integrated with our new scheme, outperforms the standard iBP on a set of NMR-like instances.
Subject: Geometria de distânciasAlgoritmos branch-and-pruneÁrvores (Teoria dos grafos)Ressonância magnética nuclearGeometria molecular
Country: Polônia
Editor: Institute of Electrical and Electronics Engineers
Citation: 2014 Federated Conference On Computer Science And Information Systems, Fedcsis 2014. Institute Of Electrical And Electronics Engineers Inc., v. , n. , p. 457 - 463, 2014.
Rights: fechado
Identifier DOI: 10.15439/2014F92
Address: https://annals-csis.org/Volume_2/drp/92.html
Date Issue: 2014
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-84912084075.pdf213.25 kBAdobe PDFView/Open


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