A symmetry-driven BP algorithm for the Discretizable Molecular Distance Geometry Problem

Abstract : Branch & Prune (BP) is a deterministic algorithm for the solution of the Discretizable Molecular Distance Geometry Problem (DMDGP). This problem has important applications in the field of structural biology, in particular for the determination of the three-dimensional conformation of a molecule by using information obtained by NMR techniques. In recent works, we proved that the search domain of the DMDGP, which is represented by a binary tree, contains various symmetries which are related to the number of solutions to the problem. In the present work, we propose a variant of the BP algorithm which is able to exploit the information regarding the symmetries to speed up the search. Computational experiments show that the symmetry-driven BP (symBP) outperforms the original BP algorithm in particular when instances having several solutions are considered.
Type de document :
Communication dans un congrès
IEEE International Conference on Bioinformatics and Biomedicine, Nov 2011, Atlanta, United States. IEEE, 2011
Liste complète des métadonnées

https://hal.inria.fr/inria-00637771
Contributeur : Antonio Mucherino <>
Soumis le : mercredi 2 novembre 2011 - 18:57:31
Dernière modification le : mercredi 16 mai 2018 - 11:23:05

Identifiants

  • HAL Id : inria-00637771, version 1

Citation

Antonio Mucherino, Carlile Lavor, Leo Liberti. A symmetry-driven BP algorithm for the Discretizable Molecular Distance Geometry Problem. IEEE International Conference on Bioinformatics and Biomedicine, Nov 2011, Atlanta, United States. IEEE, 2011. 〈inria-00637771〉

Partager

Métriques

Consultations de la notice

477