A new algorithm for the ^KDMDGP subclass of Distance Geometry Problems

DOI10.1007/S00453-021-00835-6MaRDI QIDQ6348899arXivFDO

Authors Douglas S. Gonçalves, Carlile Lavor, Leo Liberti, Michael Souza

Publication date 11 September 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00453-021-00835-6

Mathematics Subject Classification ID

General theory of distance geometry (51K05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05)

arXiv classification

cs.DMmath.CO

Abstract: The fundamental inverse problem in distance geometry is the one of finding positions from inter-point distances. The Discretizable Molecular Distance Geometry Problem (DMDGP) is a subclass of the Distance Geometry Problem (DGP) whose search space can be discretized and represented by a binary tree, which can be explored by a Branch-and-Prune (BP) algorithm. It turns out that this combinatorial search space possesses many interesting symmetry properties that were studied in the last decade. In this paper, we present a new algorithm for this subclass of the DGP, which exploits DMDGP symmetries more effectively than its predecessors. Computational results show that the speedup, with respect to the classic BP algorithm, is considerable for sparse DMDGP instances related to protein conformation.

This page was built for publication: A new algorithm for the $^K$DMDGP subclass of Distance Geometry Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348899)