TY - GEN
T1 - A symmetry-driven BP algorithm for the discretizable molecular distance geometry problem
AU - Mucherino, A.
AU - Lavor, C.
AU - Liberti, L.
PY - 2011/12/1
Y1 - 2011/12/1
N2 - 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.
AB - 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.
U2 - 10.1109/BIBMW.2011.6112403
DO - 10.1109/BIBMW.2011.6112403
M3 - Conference contribution
AN - SCOPUS:84856002031
SN - 9781457716133
T3 - 2011 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2011
SP - 390
EP - 395
BT - 2011 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2011
T2 - 2011 IEEE International Conference onBioinformatics and Biomedicine Workshops, BIBMW 2011
Y2 - 12 November 2011 through 15 November 2011
ER -