TY - GEN
T1 - Comparisons between an exact and a metaheuristic algorithm for the molecular distance geometry problem
AU - Mucherino, Antonio
AU - Liberti, Leo
AU - Lavor, Carlile
AU - Maculan, Nelson
PY - 2009/1/1
Y1 - 2009/1/1
N2 - We consider the Discretizable Molecular Distance Geometry Problem (DMDGP), which consists in a subclass of instances of the distance geometry problem related to molecular conformations for which a combinatorial reformulation can be supplied. We investigate the performances of two different algorithms for solving the DMDGP. The first one is the Branch and Prune (BP) algorithm, an exact algorithm that is strongly based on the structure of the combinatorial problem. The second one is the Monkey Search (MS) algorithm, a meta-heuristic algorithm that is inspired by the behavior of a monkey climbing trees in search for food supplies, and that exploits ideas and strategies from other meta-heuristic searches, such Genetic Algorithms, Differential Evolution, and so on. The comparison between the two algorithms is performed on a set of instances related to protein conformations. The used instances simulate data obtained from the Nuclear Magnetic Resonance (NMR), because the typical distances provided by NMR are considered and a predetermined number of wrong distances are included.
AB - We consider the Discretizable Molecular Distance Geometry Problem (DMDGP), which consists in a subclass of instances of the distance geometry problem related to molecular conformations for which a combinatorial reformulation can be supplied. We investigate the performances of two different algorithms for solving the DMDGP. The first one is the Branch and Prune (BP) algorithm, an exact algorithm that is strongly based on the structure of the combinatorial problem. The second one is the Monkey Search (MS) algorithm, a meta-heuristic algorithm that is inspired by the behavior of a monkey climbing trees in search for food supplies, and that exploits ideas and strategies from other meta-heuristic searches, such Genetic Algorithms, Differential Evolution, and so on. The comparison between the two algorithms is performed on a set of instances related to protein conformations. The used instances simulate data obtained from the Nuclear Magnetic Resonance (NMR), because the typical distances provided by NMR are considered and a predetermined number of wrong distances are included.
KW - Branch and prune
KW - Combinatorial optimization
KW - Distance geometry
KW - Monkey search
KW - Protein molecules
UR - https://www.scopus.com/pages/publications/72749092411
U2 - 10.1145/1569901.1569948
DO - 10.1145/1569901.1569948
M3 - Conference contribution
AN - SCOPUS:72749092411
SN - 9781605583259
T3 - Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009
SP - 333
EP - 340
BT - Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009
PB - Association for Computing Machinery (ACM)
T2 - 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009
Y2 - 8 July 2009 through 12 July 2009
ER -