Exploiting Symmetry Properties of the Discretizable Molecular Distance Geometry Problem - Archive ouverte HAL Access content directly
Journal Articles Journal of Bioinformatics and Computational Biology Year : 2012

Exploiting Symmetry Properties of the Discretizable Molecular Distance Geometry Problem

(1) , (2) , (3)
1
2
3

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.
Not file

Dates and versions

hal-00756939 , version 1 (24-11-2012)

Identifiers

  • HAL Id : hal-00756939 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More