EXPLOITING SYMMETRY PROPERTIES OF THE DISCRETIZABLE MOLECULAR DISTANCE GEOMETRY PROBLEM

摘要

The Discretizable Molecular Distance Geometry Problem (DMDGP) involves a subset ofninstances of the distance geometry problem for which some assumptions allowing for discretizationnare satis¯ed. The search domain for the DMDGP is a binary tree that can bene±ciently explored by employing a Branch & Prune (BP) algorithm. We showed in recent worksnthat this binary tree may contain several symmetries, which are directly related to the totalnnumber of solutions of DMDGP instances. In this paper, we study the possibility of exploitingnthese symmetries for speeding up the solution of DMDGPs, and propose an extension of the BPnalgorithm that we named symmetry-driven BP (symBP). Computational experiments onnarti¯cial and protein instances are presented