Recent Developments on the Molecular Distance Geometry Problem

Antonio Mucherino

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. Such distances can be estimated through experimental techniques, such as the Nuclear Magnetic Resonance. In its basic form, the MDGP is a constraint satisfaction problem, but it is usually reformulated as a global continuous optimization problem, where a penalty function is introduced and minimized for finding solutions to the problem. In the hypothesis in which some particular assumptions are satisfied, the MDGP can also be reformulated as a combinatorial optimization problem, that is referred to as Discretizable MDGP (DMDGP). The combinatorial reformulation allows to obtain better-quality solutions to the problem by the employment of an exact algorithm. During the seminar, I'll introduce the DMDGP and I'll discuss some recent related studies. In particular, since not all the instances of the MDGP satisfy the assumptions for the DMDGP, I'll show some recent efforts which are devoted to methods for converting general instances of the MDGP into instances of the DMDGP. Finally, I'll present some strategies for the management of instances affected by experimental errors and noise.