Exploiting Symmetry Properties of the Discretizable Molecular Distance Geometry Problem

Abstract : The Discretizable Molecular Distance Geometry Problem (DMDGP) consists in 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.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-00756939
Contributor : Antonio Mucherino <>
Submitted on : Saturday, November 24, 2012 - 1:21:02 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM

Identifiers

  • HAL Id : hal-00756939, version 1

Citation

Antonio Mucherino, Carlile Lavor, Leo Liberti. Exploiting Symmetry Properties of the Discretizable Molecular Distance Geometry Problem. Journal of Bioinformatics and Computational Biology, World Scientific Publishing, 2012, 10 (3), pp.1242009(1-15). ⟨hal-00756939⟩

Share

Metrics

Record views

1296