Antonio Mucherino : June 24, 2010

The Discretizable Molecular Distance Geometry Problem

Antonio Mucherino, INRIA Lille

Thursday, June 24, 11:00 a.m. in the CERFACS conference room

Abstract:

The Molecular Distance Geometry Problem (MDGP) is the problem of finding the conformation of a molecule starting from some known distances between pairs of its atoms. The MDGP is NP-hard. 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 brings to the formulation of a combinatorial optimization problem. Even though the MDGP is still NP-hard after the discretization, instances of the problem related to real molecules can be efficiently solved by employing an ad-hoc algorithm: the Branch&Prune algorithm. Recent efforts have been devoted to the management of noise and experimental errors that can affect distances obtained by experimental techniques.