Mucherino Antonio, Lavor Carlile, Liberti Leo
IRISA, University of Rennes 1, Rennes, France.
J Bioinform Comput Biol. 2012 Jun;10(3):1242009. doi: 10.1142/S0219720012420097.
The Discretizable Molecular Distance Geometry Problem (DMDGP) involves a subset of instances of the distance geometry problem for which some assumptions allowing for discretization are satisfied. The search domain for the DMDGP is a binary tree that can be efficiently explored by employing a Branch & Prune (BP) algorithm. We showed in recent works that this binary tree may contain several symmetries, which are directly related to the total number of solutions of DMDGP instances. In this paper, we study the possibility of exploiting these symmetries for speeding up the solution of DMDGPs, and propose an extension of the BP algorithm that we named symmetry-driven BP (symBP). Computational experiments on artificial and protein instances are presented.
离散化分子距离几何问题（DMDGP）涉及距离几何问题的一部分实例，对于这些实例，满足一些允许离散化的假设。DMDGP的搜索域是一棵二叉树，可以通过使用分支与剪枝（BP）算法有效地进行探索。我们在最近的工作中表明，这棵二叉树可能包含多种对称性，这些对称性与DMDGP实例的解的总数直接相关。在本文中，我们研究利用这些对称性来加速DMDGP求解的可能性，并提出了BP算法的一种扩展，我们将其命名为对称驱动BP（symBP）。本文还给出了在人工实例和蛋白质实例上的计算实验。
