# June 24-27, 2013

## Manaus - Amazonas - Brazil

## Invited speakers

Fábio Almeida (Federal University of Rio de Janeiro, Brazil)

Gordon Crippen (University of Michigan, USA)

Michel-Marie Deza (Ecole Normale Supérieure, France)

Floor van Leeuwen (University of Cambridge, England)

Leo Liberti (École Polytechnique, France)

Therese Malliavin (Institut Pasteur - France)

Antonio Mucherino (Université de Rennes 1, France)

Nicolas Rojas (SUTD-MIT International Design Center, Singapore)

Vin de Silva (Pomona College, USA)

Amit Singer (Princeton University, USA)

Zhijun Wu (Iowa State University, USA)

Janez Žerovnik (Fakulteta za strojništvo Ljubljana, Slovenia)

##### 1- Fábio Almeida (Universidade Federal do Rio de Janeiro, Brazil)

**Discrete conformational states and the energy landscape of proteins: demand for computational methods for structure calculation of excited states**

Proteins are dynamic entities that move in a hierarchy of timescales that goes from picoseconds to seconds. The energy landscape of a protein defines the thermally accessible conformational states. The energy of each state defines the relative population and the energy of the transition-state defines protein dynamics. Motions that occur in microseconds to seconds are a result of energy barriers that are bigger than thermal energy. They are known as conformational exchange and define biologically relevant processes that are frequently involved in binding and allostery. In this talk we will show the importance of computational methods to calculate the structure of discrete excited states and to evaluate the energy landscape of proteins. We will show how the mapping of regions in conformational exchange leaded to the discovery of membrane binding sites in plant defensins. Defensins share the same fold, but display significant difference in dynamics. Structure of excited states reveals the reason of success of Cys-knot folding of defensins. We will also show how water-permeable excited states contribute to proton transfer and catalysis of thioredoxins.

##### 2- Gordon Crippen (University of Michigan, USA)

**An Alternative Approach to Distance Geometry Using $L^{\infty}$ Distances**

A standard task in distance geometry is to calculate one or more sets of Cartesian coordinates for a set of points that satisfy given geometric constraints, such as bounds on some of the $L^2$ distances. Using instead $L^{\infty}$ distances is attractive because distance constraints can be expressed as simple linear bounds on coordinates. Likewise, a given matrix of $L^{\infty}$ distances can be rather directly converted to coordinates for the points. It can happen that multiple sets of coordinates correspond precisely to the same matrix of $L^{\infty}$ distances, but the $L^2$ distances vary only modestly. Practical examples are given of calculating protein conformations from the sorts of distance constraints that one can obtain from nuclear magnetic resonance experiments.

##### 3- Michel-Marie Deza (Ecole Normale Supérieure, France)

**Distances and Geometry**

It is a tutorial-like survey, focused on definitions, of main distances used in Geometry. The Contents is: 1-) Application example: distances in Data Clustering, 2-) Birdview on metric spaces (Metric repairs, Generalizations of metric spaces, Metric transforms, Dimension, radii and other numeric invariants of metric spaces, Relevant notions: special subsets, mappings, completeness, Main classes of metric spaces), 3-) Example: distance geometry and similar graph problems, 4-) Metric/Geodesic Geometry: curves, convexity etc., and 5-) Other geometric distances (Projective and A ne Geometry, Distances on surfaces and knots, Distances on convex bodies and cones).

##### 4- Floor van Leeuwen (University of Cambridge, England)

**The self-calibrating solutions of all-sky space astrometry**

In space astrometry we determine positions of stars on the sky as a function of time, to derive their distances, distribution and motions in space. This is done by measuring at very high accuracy large angular distances between stars on the sky over a period of several years. One such experiment is finished (the Hipparcos satellite mission), and one is to be launched later this year (the Gaia satellite mission). Although this is not directly an application of distance geometry, the solution mechanisms that transfer the 13 million one-dimensional measurements of large arcs on the sky, collected over a three-year period by the Hipparcos satellite, to a final catalogue of positional information for 118000 (moving) stars, is based on similar processes and faces similar problems. I will present a brief background of space astrometry, the way it is done, and its possibilities and limitations. Then I will show the basic measurements and their characteristic features, and how one gets from these measurements to a full-sky catalogue of positional information. In particular the measurement of the stellar parallax and the overall importance in astrophysics of distance measurements will be described. Finally, some statistical properties of the catalogue are shown for a case where the calibration of the instrumental effects has not been completely successful.

##### 5- Leo Liberti (École Polytechnique, France)

**Distance Geometry: the past and the present**

We present an overview of the themes and trends in Distance Geometry (DG) from its birth to current research. Although DG appeared formally in the 1930s, some applications delve their roots in more ancient times. Famous mathematicians (such as Godel) worked in DG. Nowadays, DG is being developed by researchers in the following application fields: proteomics, wireless networks, statics, robotics and statistics. Techniques for solving DG problems include local and global optimization, semi definite programming, differential equations, polynomial rings, combinatorial analysis, group theory, oriented matroids and others.

##### 6- Thérèse Malliavin (Institut Pasteur, France)

**The protein structures as constrained geometric objects**

Proteins are polypeptides of amino-acids involved in most of the biological processes. In the last 50 years, the study of their structures at the molecular level revolutionized the vision of biology. The three-dimensional structures of the proteins are geometric objects defined by the relative positions of the protein atoms. The determination of these objects attract much interest as it is closely related to the identification of their biological function. These objects can be determined from inter-atomic distances measured by Nuclear Magnetic Resonance (NMR), and the lack of precision of the measure produces variability in the protein structure. But the variability of the protein structure does not only come from measurement imprecision, but is also due to protein conformational equilibrium, which plays a major role into biological processes. Due to this intrinsic variability, the protein structure is calculated by repeating the same optimization procedure with changing the initialization seed. The algorithm for this iterative procedure stops when the repeated protein structures are sufficiently superimposed to each other. The choice of the required level of superimposition from a Bayesian analysis of the structure determination problem permits to obtain a least-biased geometry in agreement with the best measure fit. As the protein structures are 3D Euclidean geometric objects, the inter-atomic distances are linked by triangle inequalities. In that way, the distances can be hierarchized through the estimation of their redundancy. I shall show that this redundancy can be related to experimental observations on the energetic bases of protein stability, and to protein dynamics and function.

##### 7- Antonio Mucherino (Université de Rennes 1, France)

**Discretization Orders for Distance Geometry**

The discretization of Distance Geometry Problems (DGPs) allows to reduce their search domains to trees which are binary when all distances are exact. DGPs can be therefore seen as combinatorial optimization problems, which we solve by employing an ad-hoc Branch & Prune (BP) algorithm, that is potentially able to enumerate the entire solution set. Essential for the discretization are some assumptions to be verified by DGP instances (we say that such instances belong to the DMDGP class). When DGPs related to molecules are considered, the order given to the atoms of the molecule plays an important role, because the discretizability of the instance is strongly related to this order. In this talk, I will discuss on different approaches to this ordering problem, which becomes a fundamental pre-processing step for applying BP. The case in which all distances are exact, as well as the more realistic one in which there are imprecise distances, will be discussed in details.

##### 8- Nicolas Rojas (SUTD-MIT International Design Center, Singapore)

**Distance-based formulations for the position analysis of kinematic chains**

This talk addresses the problem of finding all possible assembly modes that a multi-loop linkage can adopt. This problem arises when solving, for instance, the inverse kinematics of serial robots or the forward kinematics of parallel robots. The first step to solve it consists in deriving a set of closure conditions, that is, a set of equations that are satisfied if, and only if, the linkage is correctly assembled. Most of the current techniques use as closure conditions a set of independent loop equations. The use of independent loop equations has seldom been questioned despite the resulting system of equations becomes quite involved even for simple linkages. In this talk, it will be shown how Distance Geometry is of great help to get simpler sets of closure conditions. The developed technique will be exemplified using different Baranov trusses, Assur kinematic chains, and pin-jointed Grübler kinematic chains. As by-product of this technique, an efficient procedure for tracing coupler curves of pin-jointed linkages will be also presented.

##### 9- Vin de Silva (Pomona College, USA)

**Topological Dimensionality Reduction**

High-dimensional data sets often carry meaningful low-dimensional structures. There are different ways of extracting such structural information. The classic (circa 2000, with some anticipation in the 1990s) strategy of nonlinear dimensionality reduction (NLDR) involves exploiting geometric structure (geodesics, local linear geometry, harmonic forms etc) to find a small set of useful realvalued coordinates. The classic (circa 2000, with some anticipation in the 1990s) strategy of persistent topology calculates robust topological invariants based on a parametrized modification of homology theory. In this talk, I will describe a marriage between these two strategies, and show how persistent cohomology can be used to find circle-valued coordinate functions. I will go on to describe some applications to dynamical systems. This is joint work with Dmitry Morozov, Primoz Skraba, and Mikael Vejdemo-Johansson.

##### 10- Amit Singer (Princeton University, USA)

**Localization by Global Registration**

The distance geometry problem consists of estimating the locations of points from noisy measurements of a subset of their pair-wise distances. The problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. This talk will focus on recent divide and-conquer approaches that solve the problem in two steps: In the first step, the points are partitioned into smaller subsets and each subset is localized separately into a local map, whereas in the second step a global map is obtained by stitching together all the local maps. Results of numerical simulations demonstrate the advantages of this approach in terms of accuracy and running time.

##### 11- Zhijun Wu (Iowa State University, USA)

**Distance Geometry Optimization and Applications**

A distance geometry problem is to find the coordinates for a set of points in a given metric space given the distances for the pairs of points. The distances can be dense (given for all pairs of points) or sparse (given only for a subset of all pairs of points). They can be provided with exact values or with small errors. They may also be given with a set of ranges (lower and upper bounds). In any case, the points need to be determined to satisfy all the given distance constraints. The distance geometry problem has many important applications such as protein structure determination in biology, sensor network localization in communication, and multidimensional scaling in statistical classification. The problem can be formulated as a nonlinear system of equations or a nonlinear least-squares problem, but it is computationally intractable in general. On the other hand, in practice, many problem instances have tens of thousands of points, and an efficient and optimal solution to the problem is required. In this talk, I will give a brief review on the formulation of the distance geometry problem and its solution methods. I will then present a so-called geometric buildup method and show how it can be applied to solve a distance geometry problem efficiently and deal with various types of distance data, dense or sparse, exact or inexact, effectively. I will also show how the method can be applied to a set of distance bounds and obtain an ensemble of solutions to the problem. Some computational results on protein structure determination and sensor network localization will be demonstrated.

##### 12- Janez Žerovnik (Fakulteta za strojništvo Ljubljana, Slovenia)

**Multicoloring of 3D hexagonal graphs**

A fundamental problem that appeared in the design of cellular networks is to assign sets of channels to transmitters in order to avoid unacceptable interferences. In the 2D case, good approximation algorithms exist that use the coordinates of the nodes that run in linear time (and even constant time in parallel mode). Some results for the 3D have been recently obtained, again the coordinates are assumed to be known. Because of the importance of this information it is interesting to ask how difficiult it is, knowing the distances to the neighbors, to find an embedding of the graph that would allow assigning at least approximate coordinates. This may provide efficient methods for assigning channels to ad-hoc sensor networks.