
Jeudi 6 Octobre 2011, Antonio Mucherino (Irisa, équipe Symbiose) 

Written by Pierre PETERLONGO

The Discretizable Molecular Distance Geometry Problem.
10h30 Salle Turing
The Molecular Distance Geometry Problem (MDGP) is the problem of finding the conformation of a molecule by exploiting some known distances between pairs of its atoms. The MDGP is NPhard. In its basic form, it is a constraint satisfaction problem, and it is usually reformulated as a global continuous optimization problem. In this seminar, I will discuss a discrete reformulation of the MDGP (the Discretizable MDGP) which leads to the formulation of a combinatorial optimization problem. In order to efficiently solve this combinatorial problem, we consider a deterministic algorithm that we named Branch & Prune (BP) and that is able to provide all solutions to the problem. Since the discretization process requires some assumptions that may not be satisfied in general, recent works are devoted to the problem of transforming instances of the MDGP so that the BP algorithm can be applied for their solution after a suitable discretization.

