Invited Session Thu.2.H 3005

Thursday, 13:15 - 14:45 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]

Distance geometry and applications


Chair: Antonio Mucherino and Nelson Maculan



Thursday, 13:15 - 13:40 h, Room: H 3005, Talk 1

Carlile Lavor
A discrete approach for solving distance geometry problems related to protein structure

Coauthors: Leo Liberti, Nelson Maculan, Antonio Mucherino


Nuclear Magnetic Resonance (NMR) experiments can provide distances between pairs of hydrogens of a protein molecule. The problem of identifying the coordinates of all atoms of a molecule by exploiting the information on the distances is a
Molecular Distance Geometry Problem (MDGP). A particular ordering is given to the hydrogens and also to the atoms of the protein backbone which allows to formulate the MDGP as a combinatorial problem, called Discretizable MDGP (DMDGP). We will talk about our efforts that have been directed towards adapting the DMDGP to be an ever closer model of the actual difficulties posed by the problem of determining protein structures from NMR data.



Thursday, 13:45 - 14:10 h, Room: H 3005, Talk 2

Pedro Nucci
Solving the discretizable molecular distance geometry problem by multiple realization trees

Coauthors: Carlile Lavor, Loana T. Nogueira


The Discretizable Molecular Distance Geometry Problem (DMDGP) is a subclass of the MDGP, which can be solved using a discrete method called Branch-and-Prune (BP) algorithm. We present an initial study showing that the BP algorithm may be used differently from its original form, which fixes the initial atoms of a molecule and then branches the BP tree until the last atom is reached. Particularly, we show that the use of multiple BP trees may explore the search space faster than the original BP.



Thursday, 14:15 - 14:40 h, Room: H 3005, Talk 3

Deok-Soo Kim
Molecular distance geometry problem: A perspective from the Voronoi diagram


Molecular distance geometry problem (MDGP) is to determine the three-dimensional structure of biomolecule from a subset of distances between pairs of atoms constituting the molecule. MDGP is important because molecular structure is critically used for understanding molecular function, particularly for NMR technology. There have been various approaches for solving MDGP such as branch-and-prune, geometric build-up, global optimization, etc. It is interesting to note that it is hard to find any approach based on the Voronoi diagram despite that the MDGP is an intrinsic geometric problem among neighboring atoms. The Voronoi diagram of atoms, the additivly-weighted Voronoi diagram in computational geometric term, represents the correct proximity among atoms in a compact form and is very useful for efficiently and correctly solving any kinds of shape-related molecular structure problem. In this presentation, we will discuss a potentially useful approach to connect the Voronoi diagram of atoms with an efficient solution of the MDGP.


  There are three major facts that should be watched out for in all payday loans in the United States. The main active actual substance of Levitra Professional online - Vardenafil does not affect the seminal fluid and is not addictive.