A Parallel Version of the Branch & Prune ...
Type de document :
Communication dans un congrès avec actes
Titre :
A Parallel Version of the Branch & Prune Algorithm for the Molecular Distance Geometry Problem
Auteur(s) :
Mucherino, Antonio [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Lavor, Carlile [Auteur]
Instituto de Matemática, Estatística e Computação Científica [Brésil] [IMECC]
Liberti, Leo [Auteur]
Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
El-Ghazali, Talbi [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Lavor, Carlile [Auteur]
Instituto de Matemática, Estatística e Computação Científica [Brésil] [IMECC]
Liberti, Leo [Auteur]
Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
El-Ghazali, Talbi [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Titre de la manifestation scientifique :
Computer Systems and Applications (AICCSA), 2010 IEEE/ACS International Conference on
Ville :
Hammamet
Pays :
Tunisie
Date de début de la manifestation scientifique :
2010-05-16
Date de publication :
2010
Discipline(s) HAL :
Informatique [cs]/Autre [cs.OH]
Résumé en anglais : [en]
We consider the Molecular Distance Geometry Problem (MDGP), which is the problem of finding the conformation of a molecule from some known distances between its atoms. Such distances can be estimated by performing experiments ...
Lire la suite >We consider the Molecular Distance Geometry Problem (MDGP), which is the problem of finding the conformation of a molecule from some known distances between its atoms. Such distances can be estimated by performing experiments of Nuclear Magnetic Resonance (NMR). Unfortunately, data obtained during these experiments are usually noisy and affected by errors. In particular, some of the estimated distances can be wrong, typically because assigned to the wrong pair of atoms. When particular assumptions are satisfied, the problem can be discretized, and solved by employing an ad-hoc algorithm called Branch & Prune (BP). However, this algorithm has been proved to be less efficient than a meta-heuristic algorithm when the percentage of wrong distances is large. We propose a parallel version of the BP algorithm which is able to handle this kind of instances. The scalability of the proposed algorithm allows for solving very large instances containing wrong distances. Implementation details of the algorithm in C/MPI are discussed, and computational experiments, performed on the nation-wide grid infrastructure Grid5000, are presented.Lire moins >
Lire la suite >We consider the Molecular Distance Geometry Problem (MDGP), which is the problem of finding the conformation of a molecule from some known distances between its atoms. Such distances can be estimated by performing experiments of Nuclear Magnetic Resonance (NMR). Unfortunately, data obtained during these experiments are usually noisy and affected by errors. In particular, some of the estimated distances can be wrong, typically because assigned to the wrong pair of atoms. When particular assumptions are satisfied, the problem can be discretized, and solved by employing an ad-hoc algorithm called Branch & Prune (BP). However, this algorithm has been proved to be less efficient than a meta-heuristic algorithm when the percentage of wrong distances is large. We propose a parallel version of the BP algorithm which is able to handle this kind of instances. The scalability of the proposed algorithm allows for solving very large instances containing wrong distances. Implementation details of the algorithm in C/MPI are discussed, and computational experiments, performed on the nation-wide grid infrastructure Grid5000, are presented.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :