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.
Type de document :
Article dans une revue
Journal of Bioinformatics and Computational Biology, World Scientific Publishing, 2012, 10 (3), pp.1242009(1-15)
Liste complète des métadonnées

https://hal.inria.fr/hal-00756939
Contributeur : Antonio Mucherino <>
Soumis le : samedi 24 novembre 2012 - 13:21:02
Dernière modification le : mardi 16 janvier 2018 - 15:54:20

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

493