论文标题
$^k $ dmdgp距离几何问题的新算法
A new algorithm for the $^K$DMDGP subclass of Distance Geometry Problems
论文作者
论文摘要
距离几何形状中的基本反问题是从点距离寻找位置之一。可离散的分子距离几何问题（DMDGP）是距离几何问题（DGP）的子类，其搜索空间可以由二进制树离散和表示，可以通过分支和proune（BP）算法来探索。事实证明，这个组合搜索空间具有过去十年中研究的许多有趣的对称属性。在本文中，我们为DGP的该子类提出了一种新算法，该算法比其前身更有效地利用DMDGP对称性。计算结果表明，与经典的BP算法相关的加速度对于与蛋白质构象有关的稀疏DMDGP实例非常相当。
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.
