## 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**

**Abstract:**

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**

**Abstract:**

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

**Abstract:**

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.