to the refinement step with SPG (see Section 2.4). This refinement step allows MDJEEP
to identify solutions even when the distances in the input include error.

<figure><img src="image_19.png" /><figcaption>Figure 3.7 – The two structures computed by Java MDJEEP for instances A (pink) and B (blue) overlapped with the structure measured with X-ray crystallography (gold). Examples for four proteins: 1EZG, 2ZW2, 1MK0 and 5YIU. Underneath, we see the PDB code of the protein as well as the RMSD of the two produced structures.</figcaption></figure>

**3.6 Discussion**

In this chapter, we discussed different methods for protein structure determination,
ranging from experimental methods to distance-based approaches. Several experiments
were presented, where the problem of protein structure determination was cast as an
instance of the Discretizable Distance Geometry Problem. These instances were subsequently solved by using a Java implementation of MDJEEP which is a branch-and-prune solver written as part of this thesis. When considering real protein data, uncertainty in the input data is a significant issue for the BP methods. In the first set of experiments (Section 3.5.1) we focused on small proteins and peptides, where uncertainty in the experimental NMR data is the key issue. We showed that for these small proteins, despite a large degree of uncertainty, good quality structures may be produced by BP methods. In the next set of experiments, we focused on larger proteins and a second problem of uncertainty. When using BP algorithms, the distances relating to the covalent geometry are regarded as exact, while in practice there may be large deviations in these distances. When we do not capture these variations in the instances, this leads to a build-up of error and protein structures of poor quality. The experiments that were conducted in Section 3.5.2 confirm this hypothesis and show that there is a correlation between the size of the protein and the effect of the variations in the covalent geometry.

Future work on the topic of protein structure determination has several directions. Firstly, one strategy to solve the problem of the variations in the covalent geometry is to no longer rely on force field data for these distances. Instead, perhaps a method involving statistical analysis or machine learning may be used to identify the best distances. A work in which progress was made towards such a method can be found in [196]. It is important to capture some form of variations in these distances. For example, we may want to vary the bond angles based on the secondary structure which they are in, or the type of amino acid. Secondly, including long-range CB distances may improve the quality of the structures when working with larger proteins. These distances can be obtained from the contact maps that are created by machine learning methods. For instance, a previous version of ALPHAFOLD, created these contact maps as a final output (the current version outputs the three-dimensional structure directly [169]).

When we overcome the problem of the variance in covalent geometry, perhaps we can focus on solving larger structures using genuine NMR data. A final direction of future research is visualizing the dynamics of protein structures. This relates directly to the topic of the next chapter, which focuses on the Dynamical Distance Geometry Problem.
# DYNAMICAL DISTANCE GEOMETRY & MOTIONS

So far we have only considered static problems, where distances between objects are fixed, and where realizations of the distance graph $G$ are snapshots of structures. However, the framework of Distance Geometry may also be of interest when there is a dynamic component present. For instance, using a distance-based model may be useful in the case where we want to simulate objects in a way where specific distances between the objects are enforced. For example in applications where collisions are undesired, such as air traffic control. In this thesis, we focus on the application of human motion retargeting. We are mainly interested in the application of human motions because it opens the path to research on protein dynamics. Like human characters, proteins are skeletal structures, which means that the methods used for both applications are similar.

We will start the chapter with an introduction and definition of the Dynamical Distance Geometry Problem (Section 4.1). Next, we will discuss the application of human motion retargeting in Section 4.2. In Section 4.3 we will discuss experiments where we use Distance Geometry for the motion retargeting problem. Afterward, in Section 4.4, we discuss a new representation for human motions that was inspired by structural biology and that is useful for distance-based motion retargeting. We will end the chapter by discussing the results and exploring future lines of work (Section 4.5).
<table><tr><td>4.1</td><td>Introduction</td><td>101</td></tr><tr><td>4.2</td><td>Human motion retargeting</td><td>102</td></tr><tr><td>4.2.1</td><td>Representing human motions</td><td>103</td></tr><tr><td>4.2.2</td><td>Motion retargeting in the literature</td><td>105</td></tr><tr><td>4.3</td><td>Distance-based motion retargeting in Euler space</td><td>109</td></tr><tr><td>4.4</td><td>A representation for human motions inspired by structural biology</td><td>113</td></tr><tr><td>4.4.1</td><td>The vector-torsion representation</td><td>113</td></tr><tr><td>4.4.2</td><td>Motion analysis</td><td>117</td></tr><tr><td>4.5</td><td>Discussion & Future work</td><td>125</td></tr></table>
## 4.1 Introduction

The subclass of the DGP in the literature that relates to dynamic problems is known as the Dynamical Distance Geometry Problem (dynDGP) [4, 5]. The dynamic aspect of the subclass is captured by a set of temporal instants $T$. In the representation of the dynDGP, a vertex of our graph $G$ no longer only represents an object. Instead, it represents an object $v \in V$ at a certain point of time $t \in T$, creating a simple weighted undirected graph $G = (V \times T, E, d)$. Because our list of distances $\mathcal{D}$ may include distances between objects at different times, the mapping $d$ now maps an edge between two objects $u, v$ at times $q, t$ to a distance value:

$$d: \{u_q, v_t\} \in E \rightarrow \delta(u_q, v_t) \in \mathcal{D}. \qquad (4.1)$$

In order to define the dynDGP [26], we extend the optimization variant of the DGP that was given in Definition 2:

**Definition 8** Given a simple weighted undirected graph $G = (V \times T, E, d)$ and an integer $K \in \mathbb{Z}_+$ the optimization-based dynDGP asks to determine a realization

$$x: V \times T \rightarrow \mathbb{R}^K$$

such that a penalty function $\sigma$ is minimized.

When working on the dynDGP it is common to choose a penalty function $\sigma$ which assigns varying priorities to different distances. For example, distances between two vertices $u_q$ and $v_t$ where $q$ and $t$ are close may be given more importance. For these instances, the mapping function $d$ does not only assign a distance value to an edge $\{u_q, v_t\}$ but also a priority $\pi(u_q, v_t)$. In the following, we will suppose that these priorities $\pi(u_q, v_t)$ are normalized between 0 and 1. An example of a priority-based penalty function for the dynDGP is:

$$\sigma(x) = \sum_{\{u_q, v_t\} \in E} \pi(u_q, v_t) (\|x_u^q - x_v^t\| - \delta(u, v))^2 \qquad (4.2)$$

where $x_t^v$ is the position of the object $v$ at the time $t$. Like the penalty function described in Equation (1.4), the gradient of $\nabla\sigma(x)$ of an incumbent solution $x$ can be computed in an exact way [26].

The dynDGP has many different applications. In general, much work has been done in the context of animations and simulations. Because we are dealing with distances over
time, regarding problems as instances of the dynDGP can be very useful when we want
to enforce distances between objects in an animation or simulation. For example, in the
context of air traffic management, one evident goal is to make sure that no two airplanes
are too close to each other at the same time. In [49, 197], a model with distances between
airplanes over time is used for air-conflict resolution. Another practical application is
crowd simulation [47, 48]. In this case, the distances in the model make sure that characters
in the crowd do not walk into each other, creating collisions.

One main interest for the dynDGP is to model the various changes of protein con-
formations. When visualizing a protein moving from one conformation to another, it is
important that certain inter-atomic distances are enforced. Furthermore, unwanted colli-
sions should be avoided.

In this thesis, we focus on the application of human motion retargeting. The reason
for the choice of this topic is that the human motions are akin to protein dynamics in the
way that the main characters in the motions both have a skeletal structure. The bones in
the human character can be seen as analogous to the bonds in the protein structures. In
the next section, we will look at human motions and motion retargeting in more detail.

## 4.2 Human motion retargeting

*Human motion capture* is the process of recording the movement of human actors [198]. This procedure is widely used for Computer Generated Imagery (CGI) in the movie industry but is also important in the context of making animations for video games. Once captured and digitalized, one may want to copy the movement of the actor to an animated character. However, a problem arises when the human actor and the animated character have a different morphology. For example, the animated character may have limb sizes and proportions that are non-anthropoid. In this case, it is a challenge to copy the motion from the human to a character with different proportions. This problem is known in the literature as *motion retargeting* or *motion adaptation* [15–17, 105]. When performing motion retargeting, it is crucial that contacts between joints that were present in the original motion are transferred to the new motion. It is equally important to avoid contacts that were not there to begin with. Therefore, using distance-based models for this problem seems natural and we can consider motion retargeting as an instance of the Dynamical Distance Geometry Problem.
### 4.2.1 Representing human motions

In these motions, we have a skeletal human character that changes its posture over time. The anatomy this character can be defined by using a graph $H = (V, B)$, where a vertex $v \in V$ is a joint of the character and the edge $b \in B$ is a bone. These graphs $H$ are trees, in which every joint $v$ has a unique parent joint, assigned by a function:

$$p: v \in V \setminus \{v_0\} \to p(v).$$

To finish the representation of our characters, we need the function

$$\chi: v \in V \to \chi(v) \in \mathbb{R}^3.$$

This function maps a three-dimensional offset from every joint of the character to its unique parent joint. The value $||\chi(v)||$ corresponds to the length of the bone $\{v, p(v)\} \in B$. This function $\chi$ together with the anatomy $H$ lets us define the morphology of the skeleton $(H, \chi)$ [105].

If we add a fictive root joint $v_0$ to the tree $H$ and fix it at the position $(0, 0, 0)$, we can use the offsets between a joint $v$ and its parent defined by $\chi$ to find a realization of the initial posture $x_0$ of the skeleton:

$$x_0: v \in V \to \begin{cases} (0, 0, 0) & \text{if } v = v_0, \\ \chi(p(v)) + \chi(v) & \text{otherwise.} \end{cases}$$

Figure 4.1 shows an example of a commonly used initial posture for these human motions. The motion itself is then defined by the changing positions of the joints $V$ over time. Time is defined by a series of frames $m$ frames $t \in T$, with $T = \{1, 2, \dots, m\}$. A straightforward choice for representing the motion of the character would be to use Cartesian coordinates to assign a three-dimensional position to each joint changing over time. In this case, we may extend the function $\chi$ and let it vary for every frame $t$:

$$x_t: v \in V \to \begin{cases} (0, 0, 0) & \text{if } v = v_0, \\ \chi_t(p(v)) + \chi_t(v) & \text{otherwise.} \end{cases} \quad (4.3)$$

However, this simple Cartesian representation has one large drawback: the morphology of the skeleton is not explicitly captured. When we generate new motions (for instance when we perform motion retargeting) there is a chance that the bone lengths will not be
<figure><img src="image_20.png" /><figcaption>Figure 4.1 – An example of a skeletal structure ($H, \chi$). The initial T-pose along with the labels are commonly used in BVH files [199]. Joints with $|\chi| = 0$ are shown next to their parent joint, marked in italics. For the arm, only the left-side joints are labeled, for the legs only the right-side labels are shown. The root of the tree $H$ is the “Hips” joint. Note that this is the original root of $H$, and not the fictive root node $v_0$, which is instead placed at the origin of the coordinate system. This image and other human motion images that we will present in this thesis are generated using the free software Blender<fnref n="1" />.</figcaption></figure>

constant throughout the animation. To be able to encapsulate the constant nature of the bone lengths, the standard way of describing human motions utilizes an Euler angle representation $\rho$. At every frame $t$, we assign a triplet of Euler angles $\theta$ (pitch), $\phi$ (roll), and $\eta$ (yaw) to every bone of the skeletal structure representing our character. Together with the known offset between $p(v)$ and $v$, we can define a transformation matrix $M_t(v)$ that takes into consideration both the translation data from $\chi(v)$ and the given Euler angles. A precise expansion of the matrix $M_t(v)$, based on a compound rotation matrix $R$ as well as three translation matrices, can be found in [199]. To compute the position of the joint $v$, all offsets and all Euler angles from the root node of $H$ up to $v$ need to be taken into consideration. The formula capable of converting the Euler angles in absolute

<footnote n="1">1. https://www.blender.org</footnote>
positions for the joints is therefore:

$$ \rho_t : v \in V \rightarrow \begin{cases} (0,0,0) & \text{if } v = v_0, \\ \prod_{k \in P(v)} (M_t(k)[0,0,0,1])^T & \text{otherwise,} \end{cases} \quad (4.4) $$

where $P(v)$ is set of vertices $u$ that form the unique path from $v_0$ to $v$ over the tree structure of the graph. See [199] for a more detailed examination of the Euler angle representations. In fact, the Euler representation is the one used in the BVH file format, which is discussed in the same reference, and which is the standard format for human motions. In this representation, only the rotation of the bones changes throughout the motion, which means that the bone lengths remain constant. Note that $\rho$ uses 3 degrees of freedom per bone, which is comparable to the degrees of freedom of the Cartesian representation (see Equation (4.3)). However, it is possible to represent these human motions while using fewer degrees of freedom, while still keeping the constant morphology. More detail on this will be given in Section 4.4.

### 4.2.2 Motion retargeting in the literature

When we perform motion retargeting [15], the interest is in adapting an original motion, given for the character $(H, \chi)$, to a character having a different morphology $(H, \tilde{\chi})$. Note that both characters have the same anatomy $H$. We will refer to the newly generated motion as the *target motion*. One of the most straightforward ways to generate the target motion is by Euler angle transfer. For each frame, one simply copies the Euler angles $(\theta, \phi, \eta)$ from the original joints to the joints of the target morphology. While this is easily accomplished, it can quickly lead to problems in the output motion. The most common problems that arise when using this method are that desired inter-joint contacts are not preserved in the output method and that unwanted collisions may be introduced. Examples of this are shown in Figure 4.2. To solve this problem, several methods are introduced in the literature.

In [15], a non-linear constrained optimization method was used for motion retargeting. First, important features in the original motion are identified, such as the feet of a character touching the ground. Non-distance-based features were used as well, such as the vector between two points having a specific orientation. For each of these features, a constraint is introduced. Solutions are obtained by scaling the original motion while observing the various constraints. A method that is closer to Distance Geometry was
<figure><img src="image_21.png" /><figcaption>Figure 4.2 – Simple examples of frames in motions retargeted using the Euler angle transfer method, where the motion is retargeted to a character with shorter shoulders. Two frames are selected of a motion with a character dancing the well-known “Macarena” dance. On the left, we see a frame where the character puts their hands on their head. In the retargeted motion we see that a collision is introduced, where the hands are inserted in the head. On the right, we see another frame where an undesired contact is introduced in the retargeted motion.</figcaption></figure>

proposed in [16]. Here, *interaction meshes* are used to represent the spatial relationships between nearby body parts. Then, target motions are generated by transforming these interaction meshes directly using Laplacian deformation techniques. In [17], many other methods are surveyed, including approaches that make use of statistics to perform motion retargeting.

We will now focus on methods that are based on Distance Geometry and which regard motion retargeting as an instance of the Dynamical Distance Geometry Problem, where inter-joint distances are considered and the temporal instants correspond to the frames *T*. The distance-based approach is natural considering that one of the goals of motion retargeting is to retain contacts that were present in the original motion and avoid collisions that were not. This can be achieved by enforcing certain distances between joints in the target motion. In the literature, only inter-joint distances at the same frame *t* were considered [105, 106], and instead of solving the dynDGP in one shot, it was solved as a series of static DGP instances. At every frame *t*, we have the DGP instance *G* = (*V*, *E*, *d*), where the objects *V* are the joints of the human character and the edges *E* combined with
the mapping $d$ represent inter-joint target distances. Some of these distances relate to the bones $B$ of the anatomy of the skeleton, while others are between joints that are connected via a series of bones in the anatomy. The target distances for the target motion are obtained by transforming the inter-joint distances of the original motion. The transformation is done by first normalizing the distances in the original motion, using the morphology of the original skeleton. Then, the target distances are computed by “denormalizing” the distances using the morphology of the target character. When we have computed all the distances, instead of solving the dynDGP instance in one shot, at every frame, we solve an instance of a static DGP. Afterward, the resulting poses are combined into one smooth animation using standard animation techniques.

The input for the method is the original human motion as a BVH file (the standard motion capture format) as well as the morphology ($H, \hat{\chi}$) of the target character. An overview of the full procedure is given below.

1. For each frame $t$:

(a) Derive Cartesian coordinates for each joint $v$, obtaining the pose $x_t$ in the original motion

(b) For every pair $(u, v)$ compute the target distance $\delta(u, v)$ by normalizing and denormalizing the distances in the original motion

(c) Assign priorities $\pi(u, v)$ to the target distances

(d) Solve the DGP instance arising from these target distances, obtaining the (Cartesian) pose $\hat{x}_t$ for the target motion

2. Combine resulting poses $\hat{x}_t$ into one animation

The first step (a) in the procedure is straightforward and involves converting from Euler space to Euclidean space and computing several distances. Step (b), the normalization and denormalization step, is more complicated. To achieve this, we start by computing all shortest paths $P(u, v) = \{w_1, \dots, w_k\}$ between pairs of distinct vertices, where $w_1 = u$, $w_k = v$ and, for every $i = 1, \dots, k-1$, we have $\{w_i, w_{i+1}\} \in E$ (notice that the term “shortest” makes reference to the number of edges that need to be crossed by the path to walk from the vertex $u$ to the vertex $v$ of the anatomy graph $H$). To normalize a distance $\delta(u, v)$, it is divided by the weight $s(u, v)$ of the shortest path $P(u, v)$ connecting $u$ to $v$ in the morphology. The weight $s(u, v)$ of the chain $P(u, v)$ can be computed by combining
the lengths of the bones we need to cross to get from u to v in the anatomy:

$$s(u, v) = \sum_{i=1}^{(|P(u,v)|-1)} \|\chi(w_i) - \chi(w_{i+1})\|. \qquad (4.5)$$

Note that the weight of a chain $s(u, v)$ in the original morphology $\chi$ is not the same as the weight $\hat{s}(u, v)$ in the target morphology $\hat{\chi}$, because the bone lengths are different between the morphologies. For each pair of joints $(u, v)$, the denormalized target distance (at frame $t$) is computed as:

$$\delta(u, v) = \hat{s}(u, v) \cdot \frac{\|x_u^t - x_v^t\|}{s(u, v)}, \qquad (4.6)$$

where $x_v^t$ is the position of $v$ at frame $t$ in the original motion.

The kinetic chains $P(u, v)$ are also used for step (c) where we assign priorities $\pi(u, v)$ to each target distance. The idea is that distances that relate to joints that are close together in the anatomy should have higher priorities. This means that the smaller the cardinality of the path $P(u, v)$, the higher the priority $\pi(u, v)$ should be. We start by identifying the longest chain $P_{max}$ between any two joints in the anatomy, and use this to determine the priority for any pair of joints $(u, v)$:

$$\pi(u, v) = \frac{|P_{\max}| - |P(u, v)| + 2}{|P_{\max}|} \qquad (4.7)$$

Note that when $\delta(u, v)$ relates to a bone length, $|P(u, v)| = 2$, which means that $\pi(u, v) = 1$, which is the maximal priority value. After we have all the distances and priorities, the DGP can be solved by minimizing the penalty function in Equation (4.2). Because the gradient of this penalty function $\sigma$ can be computed exactly, a logical choice is an optimization method that relies on gradient descent. In [105, 106] a SPG method similar to the refinement step for MDJEEP was used. For more information about SPG, see Section 1.4.5. When solving for $x_t$, the starting point of the optimization is the result for the previous frame $x_{t-1}$.

This distance-based approach gives good results and results in retargeted motions where undesired collisions are avoided and desired contacts are retained (see [105, 106]). However, there is one drawback to this method and results as presented in the literature. Throughout the process, the poses $x_t$ and $\hat{x}_t$ are represented in the Cartesian way (see Equation (4.3)), instead of using the popular Euler angle method. This way, the penalty function $\sigma$ is easily computed and its gradient is exact. However, as we noted in
the previous section, when we use this representation we cannot guarantee that the bone lengths are constant. In fact, SPG may slightly perturb the bone lengths at each frame. This is partly mitigated by the fact that large priority values $\pi(u, v)$ are used when the edge $\{u, v\}$ corresponds to a bone $b$ in the anatomy. In this case SPG will be less likely to change the length of $b$. In the next section, we present a different approach that solves this problem entirely, where the poses $x_t$ are represented directly in Euler space.

## 4.3 Distance-based motion retargeting in Euler space

In this section, we will present a method that extends and improves the motion retargeting approach from [105, 106]. More details on the extension and the new experiments are found in [18]. Several new ingredients are added to the approach. In general, the goal was to address two issues with the original distance-based method. Firstly, because we have no inter-frame distances in the instances, the step from one frame to another can theoretically be quite large. This leads to potential issues for the last step of the method, where the poses are combined into one smooth animation. The second problem arises when we use the Cartesian representation for poses $x_t$, as this way we allow the method to change the bone lengths from frame to frame.

To address the first problem, new inter-frame distances are introduced into the instances, between joints in subsequent frames. We include all distances between pairs of joints in subsequent frames, where the distance values are taken straight from the original motion. This means that the DGP instances at each frame no longer only contain the target distances that result from the normalization and denormalization process. Despite these new inter-frame distances, we still solve the problem frame by frame. The distance function $\delta$ for the DGP instance at frame $t$ will then look like this:

$$ \delta : \{u_q, v_t\} \in E \rightarrow \begin{cases} \frac{\hat{s}(u, v)}{s(u, v)} \|x_u^t - x_v^t\|, & \text{if } t = q, \\ \|x_u^q - x_v^t\|, & \text{if } u = v \text{ and } q = t - 1, \end{cases} $$

Apart from introducing these new distances, the way priorities $\pi$ are assigned is also changed. Firstly, the newly introduced inter-frame distances are assigned the maximal priority of 1. For the other distances, the revisited approach improves the priority calculation by exploiting the information given by the interaction distance [200] between two
joints $u$ and $v$ at a certain time frame $t \in T$. The interaction distance allows us to predict the distance that the two joints *will have* if their current relative movement (computed by comparing the current joint positions with the positions of the same joints at the previous frame) will not change in the subsequent frames. When two joints are moving one towards the other, their relative distances over time are important for performing the adaptation. This is because they can guide the movement towards a joint contact that we want to preserve. Alternatively, the relative distance over time will indicate potential self-contacts in approaching joints that we wish to avoid. Therefore, we also assign a higher priority to the distances between joints $u$ and $v$ for which the corresponding interaction distance $I(u_t, v_t)$ is smaller than a given positive threshold $\Delta$. To sum up, the new $\pi$ function has the following form:

$$ \pi : \{u_q, v_t\} \in E \rightarrow \begin{cases} 1, & \text{if } q = t - 1, \\ 1, & \text{if } q = t \text{ and } I(u_q, v_t) < \Delta), \\ \frac{\left|P_{\text{max}}\right| - \left|P_{uv}\right| + 2}{\left|P_{\text{max}}\right|}, & \text{otherwise.} \end{cases} $$

To address the problem regarding the flexibility of the bone lengths, we instead represent the poses of the target motion directly in Euler angle space. SPG then works by permuting the Euler angle variables, which makes sure that we will not be able to change the length of the bones of the character in the target motion. Furthermore, it makes it possible to easily output the BVH files for the resulting target motion. However, it complicates several of the steps of SPG. When we have an incumbent solution $\hat{x}_t$ and we want to compute the penalty function $\sigma(\hat{x}_t)$, we first have to convert from Euler space to Cartesian space so that we may compute the Euclidean distances (see Equation (4.4)). Therefore, the gradient $\nabla\sigma(\hat{x}_t)$ is no longer easily computed, because we have to also capture the conversion from Euler space to Cartesian space in the derivation. In practice, instead of using the exact derivation, we relied on numerical differentiation, using finite differences methods [121]. Specifically, we used the five-point stencil. While this kind of differentiation is slow, we do not have many vertices (joints) $V$ in the instances, so for this application, it works quite well.

This new motion adaptation method was programmed in Java, and several experiments were conducted on human motions from the Graphics Lab Motion Capture Database,<fnref n="2" /> provided by Carnegie Mellon University. Our Java code accepts a BVH file in input,

<footnote n="2">2. https://mocap.cs.cmu.edu</footnote>
containing the original motion, and outputs the retargeted motion in the same format. We will not report the numerical values of the stress function for the frames of the obtained motions because they do not always reflect the visual correctness of the postures and the movements. Instead, we compare the motions that we generate to the motions that are obtained by Euler angle transfer. The first motion that we consider is the “Macarena” dance (database entry code 135_35, see Figure 4.3). At a certain point, the character is supposed to place both hands on its head. The original frame is shown in the left-most image in Figure 4.3.

<figure><img src="image_22.png" /><figcaption>Figure 4.3 – A frame from a motion representing the macarena dance. From left to right: the posture in the original frame; the posture modified by simply transferring the original Euler angles to the different morphology; the posture obtained by our distance-based motion adaptation. The shoulders are 30% shorter in the target character as compared to the original animation.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 4.4 – Another frame for the macarena dance. From left to right: the posture in the original frame; the posture modified by simply transferring the original Euler angles to the different morphology; the posture obtained by our distance-based motion adaptation. The shoulders are 30% shorter in the target character. The distance between the two hands does not exactly correspond to the original distance in our solution, but the local distances around the hands are well preserved, allowing the viewer to essentially perceive the same posture.</figcaption></figure>
We can notice that, when the shoulders are reduced in length (–30%) and the original Euler angles are simply transferred to the new character (see central image), the two hands approach each other too much, and if one imagines where the head of the character is supposed to be, the viewer has the impression that the hands penetrate the character head. In the right-most image in Figure 4.3, our solution shows a correct adaptation of the Euler angles to preserve the distance between the hands. In the same motion, the hands of the character are placed on its back a few frames later. Another undesired effect in the animation appears if we simply transfer the Euler angles. Figure 4.4 compares the original, the angle-transfer result, and the result obtained with our approach. We see that in our result, the distance between the hands is retained.

The next motion shows a character that feels like it is cold. To warm up the hands, it rubs them together (entry code 79_68, see Figure 4.5). When the adapted character with broader shoulders tries to warm up the hands, its two hands are too far from each other (see central image in Figure 4.5). The right-most image shows instead that this artifact is not present in our retargeted motion. These two retargeted motions, as well as a third one, can be fully viewed in a YouTube video<fnref n="3" />.

<figure><img src="image_24.png" /><figcaption>Figure 4.5 – A frame for the character feeling cold and hence rubbing its hands. From left to right: the posture in the original frame; the posture modified by simply transferring the original Euler angles to the different morphology; the posture obtained by our distance-based motion adaptation. The shoulders are 30% longer in the target character. In the angle-transfer solution, the two hands can hardly touch one another.</figcaption></figure>

Finally, one may wonder whether we can still obtain such good results when the modifications on the bone lengths are more extreme (more than 30% modification of the original length). In this case, as expected, the results get worse and worse. To better deal with these more important changes, we have implemented an intermediate skeleton

<footnote n="3">3. https://www.youtube.com/watch?v=V5tkvTNRf1E</footnote>
approach (see Figure 4.6). The idea of using intermediate skeletons to improve the results of motion retargeting was initially proposed in [201] in an inverse kinematics approach; we have simply re-implemented it in our context. Instead of attempting to retarget a motion with large morphology changes, the idea is to perform intermediate retargetings in a sequence, in order to *smoothly* approach to the desired morphology. Every skeleton in the sequence has one or more intermediate morphologies between the original $\chi$ and the target $\hat{\chi}$. In the experiment depicted in Figure 4.6, we can see that the intermediate skeleton approach (with 5 intermediate morphologies) can improve the quality of our retargeted motions when the changes in the morphology are more drastic.

<figure><img src="image_25.png" /><figcaption>Figure 4.6 – On the right-most image, the result of retargeting the macarena dance frame shown in Figure 4.3 when the shoulders are 50% shorter. The sequence on the left side of the figure shows the 5 steps to move from a 10% modification to the final 50% modification, with a change of 10% per step, necessary to obtain a good-quality solution when the changes in the morphology are more important.</figcaption></figure>

## 4.4 A representation for human motions inspired by structural biology

Aside from these experiments, research was done on a new representation for human motions [18, 19]. In this section, we will discuss this new representation. Furthermore, we will present a statistical analysis of a motion capture database to underline the relevance of this new representation to motion retargeting.

### 4.4.1 The vector-torsion representation

It appears that the Euler representation for human motions in motion capture may have been inspired by a remarkably similar representation in robotics. Various representations are used in robotics, such as the Denavit-Hartenberg representation [202]. One of the popular representations uses a triplet of Euler angles to describe the orientation
of a robot arm, which combined with the three-dimensional position of the end-effector
makes it possible to generate a realization for the arm [203–205]. This makes for a min-
imal representation which uses 6 degrees of freedom. The use of Euler angles seems to
work well for controlling a robot arm, which was conceived to directly execute the cor-
responding angle variations. However, the use of Euler angles leads to representational
singularities for the problems of kinematic and dynamic control [206]. A singularity that
can occur using the Euler angle representation is a gimbal lock [207]. This occurs when
the middle rotation in the sequence makes the rotation axes of the first and third rotations
parallel. When these axes are parallel, a change to either the first or third Euler angle
will lead to the same rotation of the object in question (i.e., the robot arm). Essentially,
such a singularity leads to the loss of a degree of freedom. To overcome this problem, an
alternative, non-minimal representation in robotics was conceived as well, to avoid this
problem. Similarly, in the context of human motions and motion capture, the usefulness
of the Euler angles is debatable. We identify four drawbacks of the popular Euler angle
representation for motions. Firstly, as outlined in [208], and explained above, Euler angle
sequences admit different singularities, which may cause problems (such as a gimbal lock)
for the representation when the angles approach the values leading to these singularities.
Secondly, for a given bone, i.e. an edge $\{u, v\} \in E$, various combinations of Euler angles
can place the joint $v$ in the same position [209]. Thirdly, the Euler representation is not
optimal in terms of degrees of freedom. As we will see, it is possible to represent, in fact,
the same postures by employing two degrees of freedom only, instead of three, for most
of the skeleton bones. A final drawback of the use of Euler angles is that many of such
angle triplets correspond to unnatural human postures for human joints, which cannot
be filtered out, at least by simply imposing constraints on their values. This problem was
already encountered and partially addressed in [210], where the focus was specifically on
the human shoulders.

The representation that we will discuss here aims to address these problems. It was
inspired by structural biology and uses two angles that we have seen before in the previous
chapters: a vector and a torsion angle. These angles give rise to the name: the *vector-torsion* representation [18, 19]. This pair of angles will sometimes replace the triplet of
Euler angles employed for the representation of a joint. Differently from an Euler angle,
which depends only on the joint *v* itself and on its parent *p*(*v*), the *vector angle* $\zeta_v$ depends
on *v*, $p(*v*)$, as well as on ($p \circ p$)(*v*). Moreover, the *torsion angle* $\tau_v$ depends on *v*, $p(*v*)$,
($p \circ p$)(*v*), as well as on ($p \circ p \circ p$)(*v*). Despite this extra dependence, only the main joint
$v$ is indicated as a subscript of the angle names $\zeta_v$ and $\tau_v$; this is done to have a lighter notation. However, it will be supposed that, every time these two angles are taken into account, the necessary ancestors of $v$ all exist.

Given a morphology $(H, \chi)$, we can derive these angles by following the natural vertex order present in the anatomy $H$ [18, 19]:

**Definition 9** Given a skeletal structure $(H, \chi)$ and one realization $x$, the vector angle $\zeta_v$ for the joint $v$ in this realization is the **smallest angle** (in the range $[0, 180^\circ]$) formed by the line passing through $x((p \circ p)(v))$ and $x(p(v))$, and the line passing through $x(p(v))$ and $x(v)$.

We can remark that variations on values of the vector angle $\zeta_v$ imply movements of the joint $v$. However, as for the Euler angles (because three of them are necessary to reconstruct the motion for each joint), one vector angle, alone, cannot be used to fully represent the motion of $v$. We therefore couple the $\zeta_v$ angle with a torsion angle $\tau_v$, as described in [18, 19].

**Definition 10** Given a skeletal structure $(H, \chi)$ and one realization $x$, the torsion angle $\tau_v$ for the joint $v$ in this realization is the **clockwise angle** (in the range $[0, 360^\circ]$) formed by the plane defined by $x((p \circ p \circ p)(v))$, $x((p \circ p)(v))$ and $x(p(v))$, and the plane defined by $x((p \circ p)(v))$, $x(p(v))$ and $x(v)$.

When a realization $x$ preserves the morphology of the character, we can use this pair of angles combined with the bone lengths (defined by $\chi$) to find the Cartesian coordinates of any joint $v$ that has at least three ancestors. The two angles are illustrated in Figure 4.7. Note that we must use the **clockwise** and not the **smallest** angle for $\tau_v$ so that $\tau_v$ is in the $[0, 360^\circ]$ range. In fact, we see in Figure 4.7 that the vector-torsion angle pairs $(90^\circ, 90^\circ)$ (middle) and $(90^\circ, 270^\circ)$ (right) would not be distinguishable if we instead used the **smallest** angle for $\tau_v$. Using these angles, it is clear to see that the combination of $\zeta_v = 90^\circ$ and $\tau_v = 270^\circ$ leads to an unnatural position for this joint.

Not all joints $v \in V$ have the required number of three ancestors. Let $R \subset V$ be the joints with fewer than three ancestors. Every joint $r \in R$ must be represented using the triplet of Euler angles, leading to a hybrid representation:

$$ \rho' : (v, t) \in V \setminus \{v_0\} \times T \longrightarrow \left\{ \begin{array}{ll} (\theta_{p(v),v}^t, \phi_{p(v),v}^t, \eta_{p(v),v}^t) & \text{if } v \in R, \\ (\zeta_v^t, \tau_v) & \text{if } v \in V \setminus R. \end{array} \right. $$
<figure><img src="image_26.png" /><figcaption>Figure 4.7 – An example of $ζ_v$ and $τ_v$. Visible are the legs of a human skeleton, taken from a BVH file describing a running motion. The left side illustrates the vector angle $ζ_v$, which is the angle between the RightFoot, the RightLeg, and the RightUpLeg joints. The center shows how we arrive at the torsion angle $τ_v$ using two planes defined by RightFoot and its three ancestors RightLeg, RightUpLeg, and Hips (or RightHips). On the right, we see what happens when $τ_v = 270°$, while $ζ_v$ remains $90°$.</figcaption></figure>

The value that the vector-torsion representation has to offer for representing motions is that it lets us avoid several of the drawbacks of the Euler representation $\rho$ that were mentioned before. Namely, we see the following advantages:

- The combination of a vector angle with a torsion angle cannot lead to any representation singularities

- There exists a bijective correspondence between the value of the angles and the positions in space for the joints

- It exhibits only two degrees of freedom for encoding the same information comprised in a triplet of Euler angles

- It allows us to empirically constrain the feasible (and mostly continuous!) regions in the vector-torsion angle space where only natural postures for the human skeleton can be found.

The last point is of increased importance in the context of motion retargeting, as we will see in the next section.
4.4.2 Motion analysis

In this section, we present an analysis of the Graphics Lab Motion Capture Database, which is the same database that we used in the experiments discussed in Section 4.3. The database contains 2436 motion files which sum to a total of more than four million frames. In the following, we will refer to human joints with labels such as Hips, Right-Shoulder, and LeftLeg, which are taken directly from the BVH files in the database. Using the vector-torsion representation we conducted a statistical analysis of the vector angles $\zeta_v^t$ and torsion angles $\tau_v^t$ of every applicable joint $v$ at every frame $t$ of these four million frames. Using the resulting data from this experiment, we generated a heat-map scatter plot for each joint $v$. This analysis, just like the representation itself, also has its inspiration in structural biology. The plots that we will present are similar to the well-known Ramachandran plots, which analyze combinations of the $\phi$ and $\psi$ torsion angles in proteins.

Even though it is not possible to define the vector and torsion angles for the joints having fewer than three ancestors (see previous section) we performed the analysis on these joints as well. There is no need in the analysis to build up human postures, but only to *look at* the four million postures contained in the database. Therefore, for the joints missing a sufficient number of ancestors, we have simply defined a different set of “reference joints” in the graph $G$, that we subsequently use for defining the vector and torsion angles. For example, Figure 4.8 shows how we can still compute the vector-torsion angle pair for the RightLeg and LeftUpLeg, which have only two and one ancestor(s) respectively. Throughout the analysis, for joints such as these, we make sure to always use the same combination of joints when computing the angles, so that we obtain consistent results. Joints $v$ with $|\chi_v| = 0$ are omitted and they are not counted as ancestors of other joints either. For example, the LHipsJoint and the RHipsJoint (see Figure 4.1) are placed in the same position as the Hips joint, and the associated Euler angles are supposed to define the orientation for all joints that form the left and right leg, respectively. The vector-torsion representation does not use these particular joints because the two angles cannot be computed for them. Table 4.1 shows the complete set of joints for which we performed our analysis, together with the list of three reference joints used for computing the vector and the torsion angles.
<figure><img src="image_27.png" /><figcaption>Figure 4.8 – The RightLeg and the LeftUpLeg are two examples of joints that do not have enough ancestors to be represented by the vector-torsion angle pair. We can still use other consecutive reference vertices in the anatomy *H* to compute these angles and perform the same analysis for these joints. In the figure, we show the two sets of joints used to define the angles for the RightLeg and the LeftUpLeg. For the former, we used the joints RightUpLeg, Hips, and Spine (the dark blue path). For the latter, we used the joints Hips, Spine, and Spine1 (the orange path).</figcaption></figure>

<table><caption>Table 4.1 – The three reference joints for each joint that was involved in the analysis. The reference joint with the smallest numerical label is the closest; the one with the largest numerical label is instead the farthest. In some cases, the reference joints are not the joint ancestors given by the graph structure.</caption><thead><tr><th>joint</th><th>ref#1</th><th>ref#2</th><th>ref#3</th><th>all ancestors?</th></tr></thead><tbody><tr><td>Head</td><td>Neck</td><td>Spine1</td><td>Spine</td><td>Yes</td></tr><tr><td>Neck</td><td>Spine1</td><td>Spine</td><td>Hips</td><td>Yes</td></tr><tr><td>Spine1</td><td>Spine</td><td>Hips</td><td>RightUpLeg</td><td>No</td></tr><tr><td>Spine</td><td>Hips</td><td>RightUpLeg</td><td>RightLeg</td><td>No</td></tr><tr><td>LeftArm</td><td>Spine1</td><td>Spine</td><td>Hips</td><td>Yes</td></tr><tr><td>RightArm</td><td>Spine1</td><td>Spine</td><td>Hips</td><td>Yes</td></tr><tr><td>LeftForeArm</td><td>LeftArm</td><td>Spine1</td><td>Spine</td><td>Yes</td></tr><tr><td>RightForeArm</td><td>RightArm</td><td>Spine1</td><td>Spine</td><td>Yes</td></tr><tr><td>LeftHand</td><td>LeftForeArm</td><td>LeftArm</td><td>Spine1</td><td>Yes</td></tr><tr><td>RightHand</td><td>RightForeArm</td><td>RightArm</td><td>Spine1</td><td>Yes</td></tr><tr><td>LeftUpLeg</td><td>Hips</td><td>Spine</td><td>Spine1</td><td>No</td></tr><tr><td>RightUpLeg</td><td>Hips</td><td>Spine</td><td>Spine1</td><td>No</td></tr><tr><td>LeftLeg</td><td>LeftUpLeg</td><td>Hips</td><td>Spine</td><td>No</td></tr><tr><td>RightLeg</td><td>RightUpLeg</td><td>Hips</td><td>Spine</td><td>No</td></tr><tr><td>LeftFoot</td><td>LeftLeg</td><td>LeftUpLeg</td><td>Hips</td><td>Yes</td></tr><tr><td>RightFoot</td><td>RightLeg</td><td>RightUpLeg</td><td>Hips</td><td>Yes</td></tr><tr><td>LeftToeBase</td><td>LeftFoot</td><td>LeftLeg</td><td>LeftUpLeg</td><td>Yes</td></tr><tr><td>RightToeBase</td><td>RightFoot</td><td>RightLeg</td><td>RightUpLeg</td><td>Yes</td></tr></tbody></table>
We will present 18 scatter plots for different joints, starting at the head of the skeleton, and working our way down to the feet. The vector angles are shown on the x-axis and the torsion angles on the y-axis. In these plots, points tending to the warmer colors correspond to pairs of angles that were found more frequently.

<figure><img src="image_28.png" /><figcaption>Figure 4.9 – The plot for the Head.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>Figure 4.10 – The plot for the Neck. The encircled points correspond to the unnatural position seen on the right in Figure 4.27</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>Figure 4.11 – The plot for the Spine1.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>Figure 4.12 – The plot for the Spine.</figcaption></figure>

Figure 4.9 shows the scatter plot for the human head. As expected, this joint is not able to perform much movement in the space defined by the vector and torsion angle. Roughly speaking, only one-third of this space is feasible for the head joint. Moreover, the warmer part of the scatter plot indicates that the most common posture for this joint is when the two angles are close to 180°, which is compatible with an erected posture for the upper body part. While the Neck joint (Figure 4.10) exhibits a pattern very similar
to the one of the Head joint, we notice that the two joints involved in the modeling of the human spine (see Figure 4.11 and 4.12) admit an even smaller feasible space. This is particularly true for the Spine1 joint, where a large part of the scatter plot remained white which means that the combinations of vector and torsion angles in these areas are completely infeasible for a human spine.

<figure><img src="image_32.png" /><figcaption>Figure 4.13 – The plot for the LeftArm.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>Figure 4.14 – The plot for the RightArm.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>Figure 4.15 – The plot for the LeftForeArm.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>Figure 4.16 – The plot for the RightForeArm. The encircled points correspond to the unnatural position seen on the right in Figure 4.27.</figcaption></figure>

The plots for the LeftArm (Figure 4.13) and RightArm (Figure 4.14) show a quite constrained pattern as well, which is similar to those found for some of the previous joints but shifted in the center of the vector angle axis (the *x*-axis). This means that the angle formed by the spine and one of these two joints is often close to 90°. In fact, we see that these two joints share the same global Cartesian positions with the LeftShoulder
and RightShoulder joints. We can also remark that the two scatter plots are symmetric w.r.t. the axis parallel to the x-axis and passing through the torsion angle value 180°. The expected flexibility for the human arms is reflected in the scatter plots in Figure 4.15 and 4.16, related to the LeftForeArm and RightForeArm joints, respectively. This is the first pair of joints so far for which the “coloured areas” can cover more than 50% of the two-dimensional space. Yet, there are still particular combinations of vector and torsion angles that correspond to unnatural postures. As discussed in more detail later, the outliers found in the scatter plot concerning the RightForeArm correspond to errors that we have identified in the motion capture database. Again, the two scatter plots for the two forearms are symmetric with one another.

<figure><img src="image_36.png" /><figcaption>Figure 4.17 – The plot for the LeftHand.</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>Figure 4.18 – The plot for the RightHand.</figcaption></figure>

Similarly, Figure 4.17 and 4.18, depicting the scatter plots related to the LeftHand and RightHand joints respectively, show a quite large range of movement possibilities for these joints. This was expected as well. Moreover, the sparsely populated blue areas in these two scatter plots seem to suggest the extremely high flexibility of the human hand: even if sometimes very uncommon (a few frames of the database may contain them), there exist very special (and still natural) postures that the human hand can take. Therefore, if we take into consideration in full these low-populated areas, we can state that the scatter plots related to the human hands are the ones that almost cover the entire two-dimensional space.

When stepping down over the joints forming the human legs, we can observe similar patterns. For the upper joints in Figure 4.19 and 4.20, concerning the LeftUpLeg and the RightUpLeg joints, respectively, we can notice that the patterns are similar to those observed for the two upper arm bones. Similarly, we have the pattern of the LeftLeg
<figure><img src="image_38.png" /><figcaption>Figure 4.19 – The plot for the LeftUpLeg.</figcaption></figure>

<figure><img src="image_39.png" /><figcaption>Figure 4.20 – The plot for the RightUpLeg.</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>Figure 4.21 – The plot for the LeftLeg joint. The points in the green circle correspond to the uncommon poses in Figure 4.28.</figcaption></figure>

<figure><img src="image_41.png" /><figcaption>Figure 4.22 – The plot for the RightLeg joint. The points in the green circle correspond to the uncommon poses in Figure 4.28.</figcaption></figure>

<figure><img src="image_42.png" /><figcaption>Figure 4.23 – The plot for the LeftFoot.</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>Figure 4.24 – The plot for the RightFoot.</figcaption></figure>
joint in Figure 4.21, and the pattern of the RightLeg joint in Figure 4.22. The human feet also exhibit large movement possibilities, as we have observed for the hands, but the low-populated areas in the scatter plots for the feet are much more sparse. This can be a consequence of the fact that the human feet lost, during evolution, part of their movement possibilities, but the similarity to the hands is still visible in our figures. The scatter plot for the LeftFoot joint is in Figure 4.23; the scatter plot for the RightFoot joint is in Figure 4.24.

Finally, the LeftToeBase and RightToeBase joints, in Figure 4.25 and 4.26 respectively, show that they are the only joints that can span the entire two-dimensional space, but the region is not continuous and most of the vector-torsion combinations are placed around the center of the plot, where $\zeta_v = 90^\circ$ and $\tau_v = 180^\circ$.

<figure><img src="image_44.png" /><figcaption>Figure 4.25 – The plot for the LeftToeBase. Figure 4.26 – The plot for the RightToeBase.</figcaption></figure>

To sum up, the analysis shows that there exist large differences in flexibility between different joints, and the feasible regions tend to vary a lot based on the nature of each joint. In general, the vector angle seems to be the most restrictive factor. For joints like the Head, Neck, and Spine joints, we see that the feasible vector angle regions are around the $180^\circ$ mark and do not vary much. The plots for these joints are quite similar, and this makes sense when we look at their respective ancestor joints in the skeleton (see Figure 4.1). Joints on the right and left sides of the human body have very comparable regions, except for the fact that the values of the torsion angles are generally inverted. This is a result of the fact that we use a clockwise rotation to compute the torsion angles between the two planes defined by the quadruplets of joints. This gives rise to the symmetry property mentioned above. Various of the white regions in these scatter plots appear to be in logical positions intuitively. For instance, the example of the inverted knee (the vector-torsion
angle pair (90°, 270°)) in Figure 4.7 can be found in a (small) white region in the plot
the RightFoot joint.

One observation from the plots is that there exist various data points that appear to
be outside the “warmer”, more frequent regions. We looked at several of these deviating
data points and classified them into two categories: motion capture errors and uncommon
postures. The motions containing motion capture errors should be eventually excluded
from the data sets when using the results of the analysis. We provide some examples for
each of these categories and show that it is rather uncomplicated to distinguish between
the two. Figure 4.27 shows two instances of an erroneous pose in a human motion from
the database, where the angles lie far outside the normal ranges. Finally, we showcase two
examples of outliers that correspond to possible, yet rare, human poses. The examples
affect vector-torsion angles in at least two joints: LeftLeg and RightLeg. Figure 4.21
and 4.22 show the two plots affected by these postures, with the outlying points encircled
in green. What these two poses have in common, is that for both the left and right sides of
the skeleton, the vector angles (between the Leg, UpLeg, and Hips joints) are quite small.
While the figure only shows two examples, there are many similar cases, for example in
the scatter plot of the UpLeg joints, there are some outlying data points where the vector
angles are smaller than 70°. These, and other data points, do correspond to valid human
postures.

<figure><img src="image_45.png" /><figcaption>Figure 4.27 – The two motion capture errors. On the left, we see a bug for the Neck (motion: #138_31, frames: 70–688). The corresponding points in the scatter plot are encircled in red in Figure 4.10. On the right, we see an error for the RightForeArm (motion: #143_38, frames: 625–660). The corresponding points in the scatter plot are encircled in red in Figure 4.16</figcaption></figure>
<figure><img src="image_46.png" /><figcaption>Figure 4.28 – Examples of outlying data points that correspond to valid human postures. Left: a frame of the character landing after a wide-legged jump (motion: #121_19, frame: 847). Right: a frame of the character in a sitting position (motion: #111_09, frame: 357).</figcaption></figure>

**4.5 Discussion & Future work**

In this chapter, we discussed several new results in the context of the Dynamical Distance Geometry Problem. In particular, we focused on the application of human motions and motion retargeting. We expanded on a distance-based method for motion retargeting, including new inter-frame distances, priorities based on the interaction distances between joints, and optimization in Euler space. Next, we looked at a new representation for human motions, inspired by the vector and torsion angles from structural biology. This representation has fewer degrees of freedom than the standard representation used in the literature. Furthermore, it allowed for a detailed analysis of a large database of human motions. This analysis lets us identify natural positions for the different joints in the human body.

This leads directly to the first area of future work. The results from this analysis can be used for motion retargeting. The constraints that we can obtain from the scatter plots may be used during the optimization, making sure that our retargeted motions will never contain the character taking an unnatural position. Furthermore, the results from the analysis may be used to generate random motions that look natural. Next, these results from the research on human motions should be applied to simulating protein dynamics and animating conformational samplings of protein structures, which was one of the main sources of our interest in the topic.
# ADAPTIVE MAPS & LINEAR PROGRAMMING

In the context of molecular biology, we saw that not only including distances but also torsion angles in the DGP instances can be beneficial. In this chapter, we will look at the application of adaptive maps, where we generate maps where the distances between the Points of Interest (POIs) on the map are not Euclidean but instead based on subjective measures of proximity, which depend on the user. One of the challenges when generating adaptive maps is to move the POIs in a way such that these *subjective distances* are satisfied while making sure the new map still resembles the old, general-purpose map. We will see that this problem of POI relocation can be formulated as a type of DGP, where we include constraints based on local orientations. These same constraints allow us to linearise the problem, making Linear Programming suitable for solving the problem.

We start with an introduction in Section 5.1. Next, in Section 5.2 we present a linear program (LP) which can solve the problem of POI relocation for adaptive maps. Computational experiments with this new LP are presented in Section 5.3. In Section 5.4 we present preliminary work on a method that exhaustively performs virtual axes rotations to find the combination of local orientations that lead to the best objective value. Finally, in Section 5.4 we end with some discussions.
<table><tr><td>5.1</td><td>Introduction</td><td>128</td></tr><tr><td>5.2</td><td>A linear program for POI relocation</td><td>130</td></tr><tr><td>5.2.1</td><td>Implementing the model</td><td>131</td></tr><tr><td>5.3</td><td>Experiments: the city of Granada</td><td>132</td></tr><tr><td>5.4</td><td>Rotating the axes</td><td>135</td></tr><tr><td>5.4.1</td><td>Experiments</td><td>136</td></tr><tr><td>5.5</td><td>Discussion</td><td>139</td></tr></table>
## 5.1 Introduction

Geographical maps have been in use by human civilizations for centuries, and are widely used in our everyday life. Early maps in history range from drawings etched on cave walls to extensive maps produced by ancient empires such as Babylon, Greece, and Rome [211]. These historic maps as well as most commonly used modern maps are topographic, which, once we have a 2D map, means that the relation between depicted elements is based on their Euclidean distance. A key point of these maps is that they are general-purpose, i.e., they are meant for widespread public use. In contrast to such a general-purpose map, an *adaptive map* is a map that is modified based on selected features that matter to a specific user [20, 21]. An example of this is a touristic map fine-tuned for pedestrians who have trouble climbing up or going down steep slopes. These users would much prefer routes between the POIs with low inclinations and would like to have a map capable of reflecting their preferences visually. Such an adaptive map can be created using *subjective distances* between a set of Points of Interest (POIs) on the original topographical map. The first reference to this type of map seems to be in 1983 [212] and in [213], where the idea was applied for generating metro maps. More recent works include [20, 21], which coined the term adaptive maps. In these works, the generation of adaptive maps was separated into three steps:

- Identifying the POIs and generating subjective distances between them

- Relocating POIs based on the subjective distances

- Modifying the original map so that the new POI locations are reflected

For this thesis, we focused only on the second step, relocating the POIs, while attempting to best satisfy the subjective distances. The input to the problem is the output of step 1: the two-dimensional positions of the POIs in the original general-purpose map and the pairwise subjective distances.

We can reformulate this problem as a type of Distance Geometry Problem. We have a graph $G = (V, E, d)$, where the vertices correspond to the POIs and the edges and their weights relate to the subjective proximities. If we were to solve the POI relocation problem using only this information, there is a chance that the given subjective distances will force the POIs to move in such a way that their (relative) output positions will not at all match their corresponding positions in the original map. This would make the third step of modifying the original map very difficult. Therefore, we would like the set of output POI positions after relocation to be topologically homeomorphic to the original
map. By using the positions of the POIs in the original map (which can be seen as an initial realization $x_0$), we can include extra information in our instances: local orientations. As previously described in Section 1.3, these are defined using four standard quadrants (NW, NE, SW, and SE). In order to include these orientations, $G$ must be a directed graph. We can then partition our edge set $E$ into the four quadrants. For example, when we have $(u, v) \in$ NW, it means that $v$ is to the North-West of $u$ in the original map. Of course, the information about the orientations should remain symmetric, i.e., if we have $(u, v) \in$ NW, we must have $(v, u) \in$ SE. Note that if a pair of POIs $(u, v)$ have the same $x$ or $y$-coordinate, $(u, v)$ will be in two of these quadrants (i.e., NW and NE), which is not a problem for our definition or our methods. When a realization $x$ satisfies all the local orientations, we say that $x$ is topologically homeomorphic to $x_0$. Using this extra information, we can define POI relocation as a variant of the optimization based DGP (see also [214]):

**Definition 11** Given a simple weighted directed graph $G = (V,E,d)$ and an initial realization $x_0$ of $G$, where

- $V$ is a set of POIs

- $E$ represents the presence of proximity information and is partitioned into the four subsets (NW, NE, SW, and SE) to encode the local orientations given in $x_0$

- the weight function $d$ provides the numerical values $\delta$ for the proximity measures

- For simplicity, $x_v$ is the $x$-coordinate and $y_v$ is the $y$-coordinate of POI $v$ in a realization $x$

find a realization $x: v \to \mathbb{R}^2$ such that a penalty function $\sigma$ is minimized,

$$ \text{s.t. :} \quad \left\{ \begin{array}{lll} \forall (u,v) \in \text{NW}, & x_u \ge x_v \quad \text{and} \quad y_u \le y_v, \\ \forall (u,v) \in \text{NE}, & x_u \le x_v \quad \text{and} \quad y_u \le y_v, \\ \forall (u,v) \in \text{SW}, & x_u \ge x_v \quad \text{and} \quad y_u \ge y_v, \\ \forall (u,v) \in \text{SE}, & x_u \le x_v \quad \text{and} \quad y_u \ge y_v, \end{array} \right. \qquad (5.1) $$

Because we are dealing with maps in dimension 2, $\sigma$ (see Equation (1.4)) can be defined as:

$$ \sigma(x) = \sum_{(u,v) \in E} \left( \sqrt{(x_v - x_u)^2 + (y_v - y_u)^2} - \delta(u, v) \right)^2 . \qquad (5.2) $$
Note that the definition of the graph $G$ allows the proximity measures $\delta(u, v)$ and $\delta(v, u)$ to be different because $G$ is directed. However, we will assume that the distance information in our instances is symmetric.

Using this definition, the POI relocation problem can be seen as a particular DGP subclass of instances, where the additional constraints on the relative orientations are enforced. In general, adding constraints to a known problem is likely to increase its complexity. In our case, while the POI relocation problem remains in the same complexity class of the generic DGP, these new constraints as well as the use of a linearizable distance measure will allow us to formulate the POI relocation problem as a linear program (LP) consisting of only real variables.

## 5.2 A linear program for POI relocation

As discussed in Section 1.4.6, Linear Programming may be used for general Distance Geometry Problems when we substitute the Euclidean distance norm with a linear one. In [31], the $L_\infty$ (see Equation (1.11)) norm was used and binary variables were introduced. In [32], both the $L_\infty$ and $L_1$ (see Equation (1.12)) norms were employed. However, this came at the price of adding binary variables and non-linear constraints which means that the complexity of the resulting algorithm is non-polynomial. Instead, in the case of the POI relocation problem as defined in Definition 11, we will see that the addition of the relative orientation constraints allows us to use continuous variables only.

We will substitute the Euclidean distance norm by using the $L_1$ norm. Because the dimension $K = 2$, the $L_1$ norm (also known as taxi or Manhattan distance) looks like this:

$$L_1(u, v) = |x_v - x_u| + |y_v - y_u|, \qquad (5.3)$$

where the symbol $| \cdot |$ represents the absolute value of a real number. We use this distance norm to define auxiliary variables $z_{uv}$. The linear model that we propose in [214] aims to minimize the sum of these auxiliary variables:

$$\min \sum_{(u,v) \in E} z_{uv}, \qquad (5.4)$$

where $z_{uv}$ is an upper bound for the absolute difference between the $L_1$ distance in our
incumbent solution $x$ and the proximity information $\delta$ in the input:

$$z_{uv} \geq |x_v - x_u| + |y_v - y_u| - \delta(u, v), \qquad (5.5)$$

Absolute values of computations can be problematic for LP solvers to deal with because their inclusion can cause the optimization problem to be non-convex and non-smooth. However, the relative orientations that we have in the input actually allow us to avoid the need for absolute values. This can be done by including two constraints on $z_{uv}$ for every quadrant. For each quadrant, the combination of these two constraints is equivalent to the inequality in Equation (5.5):

$$\left\{
\begin{array}{ll}
\forall (u, v) \in \text{NW}, & z_{uv} \geq y_v - y_u + x_u - x_v - \delta(u, v) \\
\forall (u, v) \in \text{NW}, & z_{uv} \geq \delta(u, v) - y_v + y_u - x_u + x_v \\
\forall (u, v) \in \text{NE}, & z_{uv} \geq y_v - y_u + x_v - x_u - \delta(u, v) \\
\forall (u, v) \in \text{NE}, & z_{uv} \geq \delta(u, v) - y_v + y_u - x_v + x_u \\
\forall (u, v) \in \text{SW}, & z_{uv} \geq y_u - y_v + x_u - x_v - \delta(u, v) \\
\forall (u, v) \in \text{SW}, & z_{uv} \geq \delta(u, v) - y_u + y_v - x_u + x_v \\
\forall (u, v) \in \text{SE}, & z_{uv} \geq y_u - y_v + x_v - x_u - \delta(u, v) \\
\forall (u, v) \in \text{SE}, & z_{uv} \geq \delta(u, v) - y_u + y_v - x_v + x_u
\end{array}
\right.
\qquad (5.6)$$

The objective function (5.4), the constraints (5.6), and the relative orientation constraints (5.1) together define the linear model for our problem.

## 5.2.1 Implementing the model

The model was implemented into Java, using the LP solver CPLEX [120], which has an interface for Java using the Concert Technology. The code for the model is found in the LINEARSOLVER class in the Java package (see Figure 1.4). In the model, we have two variables $x_v$ and $y_v$ for every POI $v$. Since we require that $\delta(u, v) = \delta(v, u)$, we only need to use one auxiliary variable $z_{uv}$ for the edges $\{u, v\}$ and $\{v, u\}$. This means the total number of variables in the model is $2|V| + \frac{1}{2}|E|$.

For every variable $z_{uv}$ we have two constraints, which means there is a total of $|E|$ of such constraints. In a naive implementation of the model, one could include a relative orientation constraint for every pair of vertices $(u, v)$. However, this can be improved if
we use two vertex orders $O_x$ and $O_y$. In the first order $O_x$, the POIs are sorted ascending by their $x$-coordinate in the original map $x_0$. In $O_y$, they are ordered ascending by their $y$-coordinate. Using these orders, we can simplify the relative orientation constraints. For a vertex $v$, let $u$ be its successor in $O_x$ and $w$ be its successor in $O_y$. If we then include the two constraints $v_x \le u_x$ and $v_y \le w_y$ for all the vertices $v$, (as long as the successor $u$ or $w$ exists), we only need $2(|V| - 1)$ constraints to cover all relative orientations. This leads to a total of $2(|V| - 1) + |E|$ constraints in the model.

The model at hand may be solved either by primal or dual simplex methods, and both can be used when employing the solver CPLEX. The model has more constraints than variables, which means that the dual solver should be more efficient (as per the CPLEX manual [120]). Therefore, we used the dual simplex method for the experiments in the next two sections.

## 5.3 Experiments: the city of Granada

To test the model and its implementation, we used a 10-point POI relocation instance available from [21]. These 10 POIs, and their initial coordinates (listed in Table 2 in [21]), are based on real Points of Interest in the city of Granada in Spain. These experiments were published in [214]. The subjective proximity information $\delta(u, v)$ between these POIs instances are shown in Table 5.1, which are based on walking distance. The walking distance is likely to differ from the Euclidean distance, while paths along streets resemble more L1 norm distances. To present the data visually, Figure 5.1 shows a colored map depicting the POI distance variations (when comparing the original Euclidean distances and the given proximity distances) in the instance, as well as the local orientations of the POIs. As mentioned in the previous section, we used IBM's CPLEX solver to obtain solutions to the implemented model. For this 10-point instance, the result was obtained in 0.072 seconds on a MacOS (Ventura), 32GB RAM, and with CPU Apple M1 Max (10 cores). In order to superimpose the obtained coordinates with the original map, we first center both point sets at the origin by subtracting the centroid from each point. Then, we scale both point sets so that their distances are within the same range. The obtained result, which has an objective function value equal to 10273, is shown in Figure 5.2. It is not trivial to visually validate the result. We will do this by contrasting the heatmap given in Figure 5.1 with the displacement of the POIs in our solution.
<table><caption>Table 5.1 – The walking distances between 10 pairs of POIs, that we use in our computational experiment. Reproduced from [21] (Table A1)</caption><thead><tr><th></th><th>P1</th><th>P2</th><th>P3</th><th>P4</th><th>P5</th><th>P6</th><th>P7</th><th>P8</th><th>P9</th><th>P10</th></tr></thead><tbody><tr><th>P1</th><td>0</td><td>1553</td><td>2783</td><td>3614</td><td>4240</td><td>5674</td><td>6972</td><td>6064</td><td>7408</td><td>5387</td></tr><tr><th>P2</th><td>1553</td><td>0</td><td>1674</td><td>3867</td><td>2975</td><td>5936</td><td>7234</td><td>6326</td><td>6807</td><td>4693</td></tr><tr><th>P3</th><td>2783</td><td>1674</td><td>0</td><td>3427</td><td>2118</td><td>5098</td><td>6396</td><td>5409</td><td>5950</td><td>3837</td></tr><tr><th>P4</th><td>3614</td><td>3867</td><td>3427</td><td>0</td><td>2471</td><td>2571</td><td>4609</td><td>3745</td><td>5222</td><td>3292</td></tr><tr><th>P5</th><td>4240</td><td>2975</td><td>2118</td><td>2471</td><td>0</td><td>3600</td><td>4684</td><td>3172</td><td>3840</td><td>1727</td></tr><tr><th>P6</th><td>5674</td><td>5936</td><td>5098</td><td>2571</td><td>3600</td><td>0</td><td>2569</td><td>3076</td><td>5083</td><td>3416</td></tr><tr><th>P7</th><td>6972</td><td>7234</td><td>6396</td><td>4609</td><td>4684</td><td>2569</td><td>0</td><td>2692</td><td>4966</td><td>3903</td></tr><tr><th>P8</th><td>6064</td><td>6326</td><td>5409</td><td>3745</td><td>3172</td><td>3076</td><td>2692</td><td>0</td><td>2415</td><td>1698</td></tr><tr><th>P9</th><td>7408</td><td>6807</td><td>5950</td><td>5222</td><td>3840</td><td>5083</td><td>4966</td><td>2415</td><td>0</td><td>2303</td></tr><tr><th>P10</th><td>5387</td><td>4693</td><td>3837</td><td>3292</td><td>1727</td><td>3416</td><td>3903</td><td>1698</td><td>2303</td><td>0</td></tr></tbody></table>

<figure><img src="image_47.png" /><figcaption>Figure 5.1 – Information related to the 10-point instance in [21]. Top left: a visual representation of the local orientations of the POIs in the original realization, which our linear model is supposed to preserve in the found solution. Bottom right: a heatmap, where the colors encode the difference in values between the Euclidean distances (in the original realization $x_0$) and the given proximity distances (walking distances, see Table 5.1). The lower the difference, the smaller the value attributed to the corresponding square in the heatmap; all difference values are normalized between 0 and 1.</figcaption></figure>
<figure><img src="image_48.png" /><figcaption>Figure 5.2 – The solution found by our linear model to the POI relocation problem related to data in Table 5.1. The points $P_*$ indicate the original locations of the POI in the initial map. In black, we see the new positions for the POIs.</figcaption></figure>

Let us first look at the pair P6 and P8, which correspond to a red area in our heatmap. This means that there is a large difference between the walking distance given and the Euclidean distance in $x_0$. The distance between these two POIs is supposed to get larger in the adaptive map, and we can notice that this happens in our solution. We can remark, however, that the locations of some other POIs are subject to even larger modifications, apparently contradicting our input data. For example, P9 is moved a lot, while in the heatmap P9 seems to be associated with more green squares (lower differences between walking distances and Euclidean distances). However, such POIs are actually displaced in
other to maintain their relative distances to other POIs which were moved to account
for the more red areas in the heatmap. For example, because P8 is moved South because
of the “red” edge {P6,P8}, P9 has to be moved South accordingly. Let us now consider the
point P3. Two of the edges related to P3 are “red” indicating a quite important variation
in the corresponding relative distances. However, the location of P3 does not seem to have
changed much in our adaptive map. This behavior is most likely due to the introduced
orientation constraints. In fact, P7 belongs to the SE quadrant of P10, and the little
movement it is allowed to take seems to be the consequence of the fact that P10 moved a
little in the South direction. Any other movement for P7 in the allowed quadrant would
have most likely caused larger distance penalties with its closest neighbors. In general, we
can observe that all local orientations are well respected.

**5.4 Rotating the axes**

In this section, we will present some ongoing work on the problem of POI relocation.
This work and the experimental results have not been published. However, we are prepar-
ing a journal publication based on these preliminary results and experiments, pending
some theoretical work.

The directions of the axes (North-South and East-West) that we used in the previous
sections are based on the directions of the axes in the original map. To obtain a linear
program these directions need to be fixed so that we may use them in the relative position
constraints, which allows for the linear calculation of the L₁ distances. However, it may
be observed that we are not required to use these specific directions of the axes. In fact,
different LPs may be obtained if we choose other directions as axes. These other LPs could
perhaps lead to a better objective value, which means that they yield a better approx-
imation of the subjective distances δ(u, v) that are given in the input. This introduces
the problem of finding which system of axes will yield a LP with a minimal objective
value. Different axes may be obtained by rotating the original map x₀ with an angle in
the range of [0, π/2]. However, not every rotation in this interval will lead to a different
linear program. In fact, we only need to consider ½n(n−1)+1 cases. Recall the two vertex
orders Oₓ and Oᵧ, where the POIs are sorted according to their x and y-coordinates in
x₀. When two rotation angles are sufficiently close such that they lead to the same orders
Oₓ and Oᵧ, the corresponding LPs will be identical and yield the same objective value.
Therefore, a different LP is only obtained when the rotations lead to different orders Oₓ
and $O_y$. Furthermore, we only obtain a different order if there is at least one pair of POIs $(u, v)$ such that the rotation makes either the $x$ or $y$-axis cross the line defined by $u$ and $v$.

To identify all rotations that lead to a different LP, for every pair $(u, v) \in V \times V$, we compute the positive angle $\alpha$ between the line defined by $(u, v)$ and the $x$-axis. Then, we should force $\alpha$ in the range $[0, \pi]$ by subtracting $\pi$ if necessary. If $\alpha > \pi/2$ it relates to a change in the order $O_x$. If $\alpha \le \pi/2$, the rotation relates to a change in $O_y$. Next, to find out the solution with the best objective value, we can try all possible $\frac{1}{2}n(n-1) + 1$ rotations which relate to a change in the orders. We can avoid performing the rotations numerically by instead rotating the axes virtually. If we keep a sorted list of the angles $\alpha$, we do not need the rotation of $x_0$ when we move from one LP to the next one. In fact, we only need to invert one of the inequalities relating to the relative orientation constraints.

### 5.4.1 Experiments

Several preliminary experiments were conducted with the method described above. First, the set of 10 POIs from Section 5.3 was analyzed. For each of the rotations in the range $[0, \pi/2]$, we solved the corresponding LPs, leading to the scatter plot shown in Figure 5.3.

<figure><img src="image_49.png" /><figcaption>Figure 5.3 – An analysis of the data set with 10 POIs (see Table 5.1). The $x$-axis: the virtual axes rotation in degrees. On the $y$-axis: the objective value of the corresponding LP.</figcaption></figure>
<figure><img src="image_50.png" /><figcaption>Figure 5.4 – Overlaps the original points (labeled) with the two sets of resulting points. In black, we see the solution with an objective value of 10273, and in gray we see the solution with an objective value of 7896. Gridlines are added for the points in black, showing the relative constraints relating to the pair (P4,P8) and (P1,P10) are swapped.</figcaption></figure>

We see that the different rotations lead to large variations in the objective value. The
objective value (as reported in the Section 5.3) is 10273 when we do not perform any
virtual rotation of the axes. The rotation leading to the best objective value is a very
small rotation of 0.79°, which leads to a solution with an objective value of 7896. To
study this more deeply, consider Figure 5.4, where we contrast the original position of
the POIs, with the two solutions. The solution from the LP with the virtual rotation was rotated back by 0.79° to match the axes of the original map.

The virtual rotation of 0.79° changes $O_x$, by swapping the order of two pairs of points: (P1,P10) and (P4,P8). Swapping P1 and P10 has the immediate effect of creating a larger (horizontal) distance between them in the gray solution, as compared to the black one. In the original *x*-order given by $x_0$, P4 is to the left of P8 but in the new one, we force P4 to be to the right of P8. This is visible in Figure 5.4, where we see that in the black solution with an objective value of 10273, P4 and P8 are almost on the same line, while in the new gray solution they have moved apart by quite a bit. Flipping the inequality in the two constraints decreases the error on the distances in different ways. For example, the absolute error of the distance between P2 and P4 is decreased by 351 (P2 and P4 are further away in the new (gray) solution, which better matches the subjective distances in Table 5.1). The pair (P2,P3) has a similar story, decreasing the objective value by 374. All these changes result in a large improvement of the objective value.

<table><caption>Table 5.2 – Results of using the exhaustive rotation method on various point sets.</caption><thead><tr><th>Instance</th><th>P10</th><th>P15</th><th>P21</th><th>P31</th><th>P41</th><th>P51</th><th>P61</th><th>P71</th><th>P81</th><th>P91</th></tr></thead><tbody><tr><td>LPs solved</td><td>46</td><td>106</td><td>211</td><td>466</td><td>821</td><td>1276</td><td>1831</td><td>2486</td><td>3241</td><td>4096</td></tr><tr><td>Objective No rotation</td><td>10273</td><td>14039</td><td>49.6</td><td>145.3</td><td>314.4</td><td>338</td><td>573</td><td>754.4</td><td>1040.9</td><td>1428.7</td></tr><tr><td>Objective Best rotation</td><td>7896</td><td>11400</td><td>42.5</td><td>131.8</td><td>292.1</td><td>318.9</td><td>500.3</td><td>735.1</td><td>994.3</td><td>1344.7</td></tr><tr><td>Improvement</td><td>23.1%</td><td>18.8%</td><td>14.3%</td><td>9.3%</td><td>7.1%</td><td>5.7%</td><td>12.7%</td><td>2.6%</td><td>4.5%</td><td>5.9%</td></tr><tr><td>Best rotation (°)</td><td>0.78</td><td>19.5</td><td>24.1</td><td>85.6</td><td>30.5</td><td>4.2</td><td>15.2</td><td>14.3</td><td>24.8</td><td>14.8</td></tr><tr><td>Total time (s)</td><td>0.36</td><td>0.69</td><td>1.8</td><td>8.4</td><td>37.7</td><td>127.9</td><td>343.8</td><td>829.4</td><td>1819.4</td><td>3600.7</td></tr><tr><td>Total time (s) Warm restart</td><td>0.24</td><td>0.37</td><td>0.54</td><td>1.37</td><td>4.5</td><td>12.3</td><td>32.6</td><td>79.5</td><td>179.6</td><td>365.4</td></tr></tbody></table>

These experiments were also extended to larger data sets, with more POIs, all extracted from the city of Granada. In total, tests were run on 10 data sets, with the following number of POIs: 10, 15, 21, 31, 41, 51, 61, 71, 81, and 91. Note that the subjective distances used in the various point sets were not all of the same type, which means the absolute values of the objective function cannot be compared between the data sets. To test the efficiency of the exhaustive virtual rotation method, we used it on the above data sets, solving many different LPs in the process. For the largest point set, with 91 POIs,
a total of 4096 LPs was solved. The results of these experiments are shown in Table 5.2. The tests were run on the same system described in Section 5.3 and using the academic version of the CPLEX solver.

In the table, we see that rotating the axes can lead to a significant improvement of the objective value, which validates the use of the method. One drawback seems to be that the larger the size of the set of POIs, the larger the number of rotations that we should try to find the best axes for the problem. This is especially reflected in the penultimate row of the table, where we see that the total running time of the method goes up to one hour. However, in practice, the running time can be much reduced by the use of *warm restarts* when solving the LPs. When we go from one virtual rotation to the next, only one inequality is inverted in the new LP compared to the previous one. Therefore, the solutions between the consecutive LPs should be rather close. If we supply the solver with the solution from the previous LP, it is able to use it as a starting point, making it find the next solution much faster. In the final column, we see the effect of including warm restarts in the procedure: the total running time is generally improved by a factor of 10. Apart from these, we can see that the relative improvement tends to decrease with the size of the instance. This is logical because the relative effect of each POI on the objective function decreases with the size of the instances.

## 5.5 Discussion

In this chapter, we used Distance Geometry to study the problem of POI relocation, which is one of the necessary steps when generating adaptive maps. Similar to the topic of structural biology, the instances for POI relocation contain more information than just pairwise distances. In the case of adaptive maps, the instances also contain relative orientations between POIs, which are included so that the generated, adapted maps have a topology that is similar to the original map. These local orientations are forced upon the generated maps in the form of linear constraints, and thus allow us to formulate a linear program for the problem. We presented in-depth experiments for a data set of 10 POIs. Aside from this, we saw that rotating the axes will lead to different local orientation constraints, which in turn lead to different linear programs. These new LPs may have better objective values, which means that the subjective distances in the input can be better approximated. We presented several preliminary experiments using an exhaustive virtual rotation method. The experiments show promising results.
Currently, work is being done on improving this method, by reducing the number of LPs that we need to solve. It is likely unnecessary to exhaustively check all possible virtual rotations. Perhaps through sensitivity analysis [215, 216], we can find certain rules that tell us beforehand whether or not a specific LP will lead to an optimal solution that is better than a previously solved LP. Theoretical research into this topic is ongoing and is expected to result in a submission to a journal.
# DISCUSSION, ONGOING AND FUTURE WORK

In this last chapter, we will summarize the results presented in the thesis. For each of the topics discussed, we will look at various avenues for further research. Finally, we will look at two projects which are ongoing work and to which only minor contributions were made as part of this thesis. For the first project (Section 6.2.1), we will look at binary representations of combinatorial problems and how we may use meta-heuristics to find solutions. This is of interest in the context of Distance Geometry because solutions to instances of the DDGP subclass may be represented using a binary string. For the second topic (Section 6.2.2), we will consider the DGP in dimension 1. In particular, we focus on one specific type of “paradoxical” instances, which appear to be trivial but are in fact hard to solve by branch-and-prune methods. We propose alternative methods, based on a matrix-by-vector reformulation, which can solve these paradoxical instances more efficiently.
<table><tr><td>6.1</td><td>Discussion and future work</td><td>143</td></tr><tr><td>6.2</td><td>Ongoing work</td><td>145</td></tr><tr><td>6.2.1</td><td>Binary representations</td><td>146</td></tr><tr><td>6.2.2</td><td>The DGP in dimension 1</td><td>147</td></tr></table>
## 6.1 Discussion and future work

In this thesis, we have discussed various aspects of Distance Geometry. The main focus was the application of structural biology using Discretizable Distance Geometry methods. A common theme in the work presented in this thesis is that not only Euclidean distances but also other geometric concepts can be exploited by DG methods.

In Chapter 2 we showed that if we include not only distance information in the instances, but also torsion angles (including their sign), this will help the branch-and-prune methods that exploit the discretizability of the instances. Specifically, the inclusion of the torsion angles will decrease the size of the tree that represents the search space. In Chapter 3, we presented two sets of experiments for the application of protein structure determination, exploiting this idea in practice. We showed that it can be desirable to not only include inter-atomic distances in the input instances, but also both proper and improper dihedral angles. We saw that when we encapsulate this information in our instances, BP methods can produce relatively good quality structures for small proteins while relying on (noisy) NMR data. However, a second set of experiments shows that there are still challenges to overcome. This is because, in the context of the BP framework, the geometric information relating to the covalent geometry of the proteins is generally regarded as constant. However, in practice, we see that there are quite large variations in this data. Despite the error-tolerance of the BP methods used, the discrepancies found within the covalent geometry make it so that the methods tend to fall short for larger proteins. Future work should focus on overcoming this problem. One strategy may be to attempt to capture these variations in the input. This could be done by using machine learning or statistical analysis in order to identify variations in the distances, for example, based on the position of the amino acid in the primary structure of the protein. This way, we may be able to use precise distances that better match the real distances in a given conformation of a protein. The second problem, the uncertainty in the instances, may be improved by including more distances. One possible new distance type that we could include is based on pairwise CB distances. These distances can be obtained from contact maps, which are produced by machine learning methods used in the context of protein structure determination [172, 173]. Contact maps give us information about CB atoms that are close in space but may be far from each other in the primary structure of the protein. This means that these distances can be very useful, as they will let us prune away large parts of the search space tree. However, the use of distances such as
these presents many new challenges. Some preliminary experiments show that the pruning
distances may be too strict and branch-and-prune will end up pruning every branch of
the tree. In these same tests, it appears that SPG is not powerful enough to permute the
incumbent solution such that these distances are satisfied. This points to an additional
point of future work, which also relates to the refinement step. We saw in this thesis that
including torsion angles and their sign is very beneficial for the BP methods. However,
in the current state, SPG only minimizes the error on the distances in the instances and
does not consider the torsion angle information at all. Including this information in the
refinement step could lead to an improvement of the generated structures. The current
implementation of SPG relies on an exact derivation of the penalty function for the gra-
dient descent. Extending this derivation to also include a violation of the dihedral angles
is not a trivial task. Furthermore, this computation may slow down the algorithm. We
did some tests with numerical differentiation methods, but these tend to be very slow. A
possible tool that could be looked into is automatic differentiation.

Aside from these specific directions and points of improvement, a more general inter-
esting direction of research is combining the discrete, BP method with machine learning.
In recent years, the most promising methods for protein structure determination have
been based on machine learning and have achieved very positive results. However, these
machine learning methods have their advantages and disadvantages. Perhaps if we could
combine our discrete method with some machine learning aspects, we could take the
best things from both worlds. A straightforward example would be to use BP as a post-
processing step after a machine learning method has produced a contact map. However,
more intricate combinations could produce better results.

In Chapter 4 we studied dynamic Distance Geometry, focusing on human motions. Our interest in human motions stems from the fact that the characters are represented using skeletal structures. Researching these human motions lays the groundwork for studying protein dynamics because proteins, like humans, also have a skeletal structure. Several experiments were presented on the subject of using DG methods for the problem of motion retargeting, where we wish to copy the motion from one actor to another character with a different morphology. Furthermore, we proposed a new (vector-torsion angle) representation for human motions, which has its roots in molecular biology. This new representation uses fewer degrees of freedom than the standard Euler angle representation. We showed that the vector-torsion angle representation is a natural fit for the application of motion retargeting. Future work directly on the topic of human motions includes expanding the
DG methods for motion retargeting. Furthermore, the vector-torsion angle representation (combined with the statistical analysis presented in Section 4.4 could potentially be used to generate random motions that guarantee that the actor always has a natural pose. Lastly, the conducted research should be extended to the subject of protein dynamics. This way, proteins moving between conformations could be visualized in an accurate way such that certain important pairwise distances (such as bond lengths and van der Waals radii) are not compromised.

In Chapter 5 we studied the application of adaptive maps. For this application, similarly to structural biology, the DGP instances also include geometric information other than Euclidean distances. For adaptive maps, we use linear distance norms and constraints based on local orientations. This special kind of DGP instances can be solved using linear models and linear programming. We presented experiments in which we solved these linear models with promising results. Furthermore, we discussed ongoing work in which different combinations of local orientations are tried by rotating the directions of the axes. In future work, we will conduct an in-depth theoretical analysis of the concept of rotating the axes and present more detailed experiments. Aside from continuing the research with a focus solely on adaptive maps, it could also be interesting to study whether these findings have any impact on other applications, such as structural biology. Perhaps the local orientations and the linear programs can be interesting for problems in that field as well.

## 6.2 Ongoing work

In this section, we will shortly discuss some ongoing work, to which the author of the thesis has contributed. This work spans two main topics which have not yet been discussed so far in the thesis. The first topic that we will discuss is binary representations of combinatorial problems and a meta-heuristics project that can be used to solve such problems. Note that the DDGP is one such combinatorial problem for which we can use a binary representation. The second topic covers the DGP in dimension 1 and two approaches that can solve a specific type of instances in this dimension.
6.2.1 Binary representations

This work concerns a project known as BINMETA<fnref n="1" /> [217], which is conceived particu-
larly to study meta-heuristic searches for global optimization problems for which a suitable
binary representation can be supplied. In such a binary representation of a solution to an
optimization problem, the smallest piece of information that we consider is a bit, while
a bit string of fixed length *n* provides the full representation. Two solutions are different
if at least one of their bits has an opposite value. The distance between two solutions
can be measured by using the Hamming distance [218], which counts the number of bits
that are different at the same positions in the two strings. Binary strings are useful for
representing problems when they admit a discrete search space.

Recall that in Chapter 2 we saw that under certain assumptions, the DDGP admits a discrete search space (see Section 2.1). In fact, the DDGP is a global optimization problem for which a binary representation comes naturally. An example of a binary tree representing the search space of an instance of the DDGP with |V| = 6 and K = 3 is given in Figure 6.1.

<figure><img src="image_51.png" /><figcaption>Figure 6.1 – An example of a tree representing the search space of an instance of the DDGP with |V| = 6 and K = 3. A path in the tree, corresponding to a possible solution to the instance is highlighted. The binary string that corresponds to the highlighted path is 100.</figcaption></figure>

Any path in this tree from the root to a leaf node corresponds to a solution for the
instance at hand. Such a path can be represented with a binary string in several ways. An
example of a simple binary representation scheme is to assign a bit for each level (vertex)
of the tree. If a bit is set to 0, it means that at the corresponding level in the tree, we
select the left candidate. If the bit is 1, we choose the right candidate. Because the first K
vertices are fixed, we only need |V| - K bits to represent a solution. The bit string that

<footnote n="1">1. https://github.com/mucherino/binMeta</footnote>
represents the highlighted solution in the tree in Figure 6.1 is 100. Every permutation of
such a bit string will correspond to a different path in the tree. For each such solution,
we know that all the reference distances are satisfied. Therefore, the quality of such a
solution may be quantified by using a penalty function that minimizes the violation of
the pruning distances.

The BINMETA project groups implementations of meta-heuristics that can be used
to solve global optimization problems as long as they admit a binary representation.
A contribution was made to this project as part of the thesis. The well-known meta-
heuristic search Variable Neighbourhood Search (VNS) was adapted to binary solutions
and Hamming space and added to the list of BINMETA implementations. More details
can be found in [219]. Future work can be done in various directions. Firstly, the different
meta-heuristic implementations should be tested in detail on instances of the DDGP. The
binary representation of the DDGP can be especially useful when the DDGP is regarded
as a series of nested subproblems, such as in [220]. The binary representations and the
meta-heuristics may be valuable in this context because we can perform contractions in
the bit strings, collapsing the solution for a subproblem into one bit. Apart from studying
the DDGP, in general, it may be interesting to investigate the meta-heuristics in the
context of problems with constraints. As mentioned before, a binary string may represent
a solution for the DDGP in which not all pruning distances are satisfied. Similarly, other
problems exist for which not all binary strings will represent feasible solutions, where all
constraints are satisfied. Particular attention should be given to the conception of the
binary representation, and the possibility of an a priori study of the implied landscapes
on the objective function.

**6.2.2 The DGP in dimension 1**

In 1979, Saxe proved that the DGP is NP-complete when *K* is set to 1 [24]. As mentioned briefly in Chapter 1, the main application of the DGP in this dimension is the clock synchronization problem [61, 71, 72], where we are given a set of clocks (represented by vertices *v* ∈ *V* and offset measurements between the clocks (the edges {*u*, *v*} ∈ *E* and the values of the weights *d*(*u*, *v*)).

As part of this thesis, contributions were made to a specific subclass of the DGP in
dimension 1. This subclass is referred to as *paradoxical* [28–30]. These kinds of instances
are represented by a graph *G* that is a cycle graph, for which a vertex order can trivially
be identified. The reason that we refer to this subclass as paradoxical is twofold. Firstly,
constructing a solution for this subclass seems relatively easy: most vertices $v$ depend only on one predecessor (reference vertex) $u$. Therefore, if we were to solve such instances using branch-and-prune, for each $v$, two new positions $x_v$ and $x_v'$ are easily identified, allowing us to build up the binary discretization tree. However, the absence of pruning distances up to the last vertex makes this class of instances very hard. Only at the very last layer of the tree, do we have access to the pruning distance between the first and last vertex, which means only then we are able to validate and prune the incorrect branches in the tree. Therefore, we first have to construct a tree of size $2^{|V|-1}$, before we can select the 2 correct solutions from all the generated realizations (paths in the tree). To avoid this issue, we proposed matrix-by-vector reformulation of this paradoxical class in [29]. This reformulation lends itself to parallelization and in two separate works we presented two different methods to solve this matrix-by-vector multiplication.

The first method, proposed in [29], is based on optical processing. Optical computing schemes have been proposed in the scientific literature to attempt to find the solutions for NP-hard problems [221–224]. We presented a new architecture for the realization of an optical processor, based on the modulation of an optical wavefront by spatial light modulators. This architecture is able to perform fast matrix-by-vector multiplication, which means that it could be used to solve instances of the paradoxical subclass of the DGP in dimension 1. Future work on this topic includes putting the optical scheme into practice and using it to solve some small instances. More details can be found in [29].

The second method, presented in [28], is implemented in C and CUDA so that the computations may be employed on the GPU. We tested this implementation with randomly generated paradoxical instances. In these experiments, the GPU implementation was compared to a branch-and-prune implementation for dimension 1. The results show that the GPU method is around 16 times faster than the BP implementation for these paradoxical instances, showing the usefulness of the matrix-by-vector reformulation.

A first line of future work exists in extending the practical experiments for the DGP in dimension 1. On a more theoretical note, it would be interesting to extend the study of the paradoxical instance class to higher dimensions.
AUTHOR'S CONTRIBUTIONS

[1] S. B. Hengeveld, T. Malliavin, J. Lin, L. Liberti, and A. Mucherino, *A Study on the Impact of the Distance Types Involved in Protein Structure Determination by NMR*, Computational Structural Bioinformatics Workshop (CSBW21), IEEE International Conference on Bioinformatics and Biomedicine (BIBM21), pp. 2502–2510, 2021.

[2] S. B. Hengeveld, M. Merabti, F. Pascale, and T. E. Malliavin, *A Study on the Covalent Geometry of Proteins and Its Impact on Distance Geometry*, International Conference on Geometric Science of Information, pp. 520–530, 2023.

[3] S. B. Hengeveld, T. E. Malliavin, L. Liberti, and A. Mucherino, *Collecting Data for Generating Distance Geometry Graphs for Protein Structure Determination*, Proceedings of Road23, 2023.

[4] S. B. Hengeveld and A. Mucherino, *On the Representation of Human Motions and Distance-based Retargeting*, 16th Conference on Computer Science and Intelligence Systems (FedCSIS21), pp. 181–189, 2021.

[5] S. B. Hengeveld and A. Mucherino, *On the Feasible Regions Delimiting Natural Human Postures in a Novel Skeletal Representation*, 17th Conference on Computer Science and Intelligence Systems (FedCSIS22), pp. 175–179, 2022.

[6] S. B. Hengeveld, F. Plastria, A. Mucherino, and D. A. Pelta, *A linear program for points of interest relocation in adaptive maps*, International Conference on Geometric Science of Information, pp. 551–559, 2023.

[7] S. B. Hengeveld and A. Mucherino, *Variable Neighborhood Search in Hamming Space*, To appear in Lecture Notes in Computer Science, Proceedings of the 14th International Conference on Large-Scale Scientific Computations (LSSC23), 2023.

[8] S. B. Hengeveld and A. Mucherino, *A GPU Approach to Distance Geometry in 1D: an Implementation in C/CUDA*, 17th Conference on Computer Science and Intelligence Systems (FedCSIS22), pp. 333–336, 2022.
[9] S. B. Hengeveld, N. R. da Silva, D. S. Gonçalves, P. H. S. Ribeiro, and A. Mucherino, *An optical processor for matrix-by-vector multiplication: an application to the distance geometry problem in 1D*, Journal of Optics, vol. 24, p. 015701, 2021.

[10] S. B. Hengeveld and A. Mucherino, *The Discrete Side of Distance Geometry: a Focus on the 1-dimensional Case*, Proceedings of Discrete Math Days, 2022.
[1] A. M.-C. So and Y. Ye, *Theory of semidefinite programming for sensor network localization*, Mathematical Programming, vol. 109, pp. 367–384, 2007.

[2] R. Harris, *Nuclear Magnetic Resonance*. 1971.

[3] A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, *Distance Geometry: Theory, Methods and Applications*. 2013.

[4] A. Mucherino and D. S. Gonçalves, *An Approach to Dynamical Distance Geometry*, Geometric Science of Information, pp. 821–829, 2017.

[5] A. Mucherino, J. Omer, L. Hoyet, P. Giordano, and F. Multon, *An application-based characterization of dynamical distance geometry problems*, Optimization Letters, vol. 14, pp. 1–15, 2020.

[6] A. Mucherino, C. Lavor, and L. Liberti, *The Discretizable Distance Geometry Problem*, Optimization Letters, vol. 6, pp. 1671–1686, 2012.

[7] A. Mucherino, L. Liberti, and C. Lavor, *MD-jeep: an Implementation of a Branch and Prune Algorithm for Distance Geometry Problems*, Lectures Notes in Computer Science 6327, K. Fukuda et al. (Eds.), Proceedings of the 3rd International Congress on Mathematical Software (ICMS10), Kobe, Japan, pp. 186–197, 2010.

[8] C. Lavor, L. Liberti, N. Maculan, and A. Mucherino, *The Discretizable Molecular Distance Geometry Problem*, Computational Optimization and Applications, vol. 52, pp. 115–146, 2012.

[9] A. Mucherino, J.-H. Lin, and D. S. Gonçalves, *A coarse-grained representation for discretizable distance geometry with interval data*, Bioinformatics and Biomedical Engineering: 7th International Work-Conference, IWBBIO 2019, pp. 3–13, 2019.

[10] A. Mucherino and C. Lavor, *The Branch and Prune Algorithm for the Molecular Distance Geometry Problem with Inexact Distances*, Proceedings of the International Conference on Computational Biology, vol. 58, pp. 349–353, 2009.
[11] C. Lavor, L. Liberti, and A. Mucherino, *The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances*, Journal of Global Optimization, vol. 56, pp. 855-871, 2013.

[12] C. Lavor, M. Souza, L. M. Carvalho, D. S. Gonçalves, and A. Mucherino, *Improving the sampling process in the interval branch-and-prune algorithm for the discretizable molecular distance geometry problem*, Applied Mathematics and Computation, vol. 389, p. 125-586, 2021.

[13] A. Mucherino, D. Gonçalves, L. Liberti, J.-H. Lin, C. Lavor, and N. Maculan, *MDjeep: a New Release for Discretizable Distance Geometry Problems with Interval Data*, IEEE Conference Proceedings, Federated Conference on Computer Science and Information Systems (FedCSIS20), Workshop on Computational Optimization (WCO20), pp. 289-294, 2020.

[14] A. Mucherino and J.-H. Lin, *An efficient exhaustive search for the discretizable distance geometry problem with interval data*, 2019 Federated Conference on Computer Science and Information Systems (FedCSIS), pp. 135-141, 2019.

[15] M. Gleicher, *Retargetting Motion to New Characters*, Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, pp. 33-42, 1998.

[16] E. S. L. Ho, T. Komura, and C.-L. Tai, *Spatial Relationship Preserving Character Motion Adaptation*, ACM Trans. Graph., vol. 29, no. 4, 2010.

[17] S. Guo, R. Southern, J. Chang, D. Greer, and J. Zhang, *Adaptive motion synthesis for virtual characters: a survey*, The Visual Computer, vol. 31, no. 5, pp. 497-512, 2015.

[18] S. B. Hengeveld and A. Mucherino, *On the Representation of Human Motions and Distance-based Retargeting*, 16th Conference on Computer Science and Intelligence Systems (FedCSIS21), pp. 181-189, 2021.

[19] S. B. Hengeveld and A. Mucherino, *On the Feasible Regions Delimiting Natural Human Postures in a Novel Skeletal Representation*, 17th Conference on Computer Science and Intelligence Systems (FedCSIS22), pp. 175-179, 2022.

[20] M. Torres Anaya, D. Pelta, and J. L. Verdegay, *A Proposal for Adaptive Maps*, pp. 657-666, 2018.
[21] M. Torres Anaya, D. Pelta, J. L. Verdegay, and C. Cruz, *Towards adaptive maps*, International Journal of Intelligent Systems, vol. 34, 2018.

[22] L. Liberti, C. Lavor, N. Maculan, and A. Mucherino, *Euclidean Distance Geometry and Applications*, SIAM Review, vol. 56, pp. 3–69, 2014.

[23] Y. Yemini, *Some Theoretical Aspects of Position-location Problems*, 20th Annual Symposium on Foundations of Computer Science, pp. 1–8, 1979.

[24] J. Saxe, *Embeddability of Weighted Graphs in K-space is Strongly NP-hard*, Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480–489, 1979.

[25] P. Duxbury, L. Granlund, S. Gujarathi, P. Juhas, and S. Billinge, *The unassigned distance geometry problem*, Discrete Applied Mathematics, vol. 204, pp. 117–132, 2016.

[26] A. Mucherino, *On the Discretization of Distance Geometry: Theory, Algorithms and Applications*, HDR Monograph, University of Rennes 1, 2018.

[27] S. B. Hengeveld, T. Malliavin, J. Lin, L. Liberti, and A. Mucherino, *A Study on the Impact of the Distance Types Involved in Protein Structure Determination by NMR*, Computational Structural Bioinformatics Workshop (CSBW21), IEEE International Conference on Bioinformatics and Biomedicine (BIBM21), pp. 2502–2510, 2021.

[28] S. B. Hengeveld and A. Mucherino, *A GPU Approach to Distance Geometry in 1D: an Implementation in C/CUDA*, 17th Conference on Computer Science and Intelligence Systems (FedCSIS22), pp. 333–336, 2022.

[29] S. B. Hengeveld, N. R. da Silva, D. S. Gonçalves, P. H. S. Ribeiro, and A. Mucherino, *An optical processor for matrix-by-vector multiplication: an application to the distance geometry problem in 1D*, Journal of Optics, vol. 24, p. 015701, 2021.

[30] S. B. Hengeveld and A. Mucherino, *The Discrete Side of Distance Geometry: a Focus on the 1-dimensional Case*, Proceedings of Discrete Math Days, 2022.

[31] G. M. Crippen, *An Alternative Approach to Distance Geometry using $L_\infty$ Distances*, Discrete Applied Mathematics, vol. 197, pp. 20–26, 2015.

[32] C. D'Ambrosio and L. Liberti, *Distance Geometry in Linearizable Norms*, Geometric Science of Information, pp. 830–837, 2017.
[33] R. S. Lima and J. Martínez, *Solving molecular Distance Geometry Problems using a continuous optimization approach*, Distance Geometry: Theory, Methods, and Applications, pp. 213–224, 2012.

[34] J. C. Gower, *Euclidean Distance Geometry*, vol. 7, 1982, pp. 1–14.

[35] A. Y. Alfakih, A. K. Khandani, and H. Wolkowicz, *Solving Euclidean Distance Matrix Completion Problems Via Semidefinite Programming*, Computational Optimization and Applications, vol. 12, pp. 13–30, 1999.

[36] I. Dokmanic, R. Parhizkar, J. Ranieri, and M. Vetterli, *Euclidean Distance Matrices: Essential theory, algorithms, and applications*, IEEE Signal Processing Magazine, vol. 32, no. 6, pp. 12–30, 2015.

[37] G. Crippen and T. Havel, *Distance Geometry and Molecular Conformation*, Chemo-metrics, vol. 15, 1988.

[38] B. Alipanahi, N. Krislock, A. Ghodsi, H. Wolkowicz, L. Donaldson, and M. Li, *Determining protein structures from NOESY distance constraints by semidefinite programming*, Journal of Computational Biology, vol. 20, pp. 296–310, 2013.

[39] W. Glunt, T. L. Hayden, and M. Raydan, *Molecular conformations from distance matrices*, Journal of Computational Chemistry, vol. 14, pp. 114–120, 1993.

[40] F. Almeida, A. Moraes, and F. Gomes-Neto, *An Overview on Protein Structure Determination by NMR: Historical and Future Perspectives of the use of Distance Geometry Methods*, Distance Geometry: Theory, Methods, and Applications, Nov. 2013.

[41] T. E. Malliavin, A. Mucherino, and M. Nilges, *Distance Geometry in Structural Biology: New Perspectives*, Distance Geometry: Theory, Methods, and Applications, pp. 329–350, 2013.

[42] I. T. Jolliffe, *Discarding Variables in a Principal Component Analysis. I: Artificial Data*, Journal of the Royal Statistical Society. Series C (Applied Statistics), vol. 21, pp. 160–173, 1972.

[43] J. J. Moré and Z. Wu, *Global continuation for distance geometry problems*, SIAM Journal on Optimization, vol. 7, pp. 814–836, 1997.

[44] J. J. Moré and Z. Wu, *Distance geometry optimization for protein structures*, Journal of Global Optimization, vol. 15, p. 219, 1999.
[45] X. Fang and K.-C. Toh, *Using a Distributed SDP Approach to Solve Simulated Protein Molecular Conformation Problems*, Distance Geometry: Theory, Methods, and Applications, A. Mucherino, C. Lavor, L. Liberti, and N. Maculan, Eds., pp. 351–376, 2013.

[46] E. F. Pettersen *et al.*, *UCSF Chimera—a visualization system for exploratory research and analysis*, Journal of computational chemistry, vol. 25, no. 13, pp. 1605–1612, 2004.

[47] D. Helbing, I. Farkas, and T. Vicsek, *Simulating dynamical features of escape panic*, Nature, vol. 407, no. 6803, pp. 487–490, 2000.

[48] A.-H. Olivier, A. Marin, A. Crétual, and J. Pettré, *Minimal predicted distance: A common metric for collision avoidance during pairwise interactions between walkers*, Gait & posture, vol. 36, no. 3, pp. 399–404, 2012.

[49] J. Omer, *A space-discretized mixed-integer linear model for air-conflict resolution with speed and heading maneuvers*, Computers & Operations Research, vol. 58, pp. 75–86, 2015.

[50] L. Asimow and B. Roth, *The rigidity of graphs*, Transactions of the American Mathematical Society, vol. 245, pp. 279–289, 1978.

[51] M. Laurent, *Cuts, matrix completions and graph rigidity*, Mathematical Programming, vol. 79, pp. 255–283, 1997.

[52] A. Alfakih, *Graph rigidity via euclidean distance matrices*, Linear Algebra and its Applications, vol. 310, no. 1-3, pp. 149–165, 2000.

[53] B. Jackson and T. Jordán, *Connected rigidity matroids and unique realizations of graphs*, Journal of Combinatorial Theory, Series B, vol. 94, no. 1, pp. 1–29, 2005.

[54] G. Laman, *On graphs and rigidity of plane skeletal structures*, Journal of Engineering mathematics, vol. 4, no. 4, pp. 331–340, 1970.

[55] B. Hendrickson, *Conditions for unique graph realizations*, SIAM journal on computing, vol. 21, no. 1, pp. 65–84, 1992.

[56] L. Hennberg, *Statik der starren systeme*, A. Bergstraesser, vol. 1, 1886.

[57] L. Cremona, *Le figure reciproche nella statica grafica*. 1879.
[58] P. Biswas, T.-C. Lian, T.-C. Wang, and Y. Ye, *Semidefinite programming based algorithms for sensor network localization*, ACM Transactions on Sensor Networks (TOSN), vol. 2, pp. 188–220, 2006.

[59] N. Krislock and H. Wolkowicz, *Explicit sensor network localization using semidefinite representations and facial reductions*, SIAM Journal on Optimization, vol. 20, pp. 2679–2708, 2010.

[60] P. Biswas, T.-C. Liang, K.-C. Toh, Y. Ye, and T.-C. Wang, *Semidefinite programming approaches for sensor network localization with noisy distance measurements*, IEEE transactions on automation science and engineering, vol. 3, no. 4, pp. 360–371, 2006.

[61] Y.-C. Wu, Q. Chaudhari, and E. Serpedin, *Clock Synchronization of Wireless Sensor Networks*, IEEE Signal Processing Magazine, vol. 28, pp. 124–138, 2011.

[62] G. Mao, B. Fidan, and B. D. Anderson, *Wireless sensor network localization techniques*, Computer networks, vol. 51, no. 10, pp. 2529–2553, 2007.

[63] M. Cao, B. D. Anderson, and A. S. Morse, *Sensor network localization with imprecise distances*, Systems & control letters, vol. 55, no. 11, pp. 887–893, 2006.

[64] S. Rai and S. Varma, *Localization in wireless sensor networks using rigid graphs: a review*, Wireless Personal Communications, vol. 96, no. 3, pp. 4467–4484, 2017.

[65] W. S. Torgerson, *Multidimensional scaling: I. Theory and method*, Psychometrika, vol. 17, no. 4, pp. 401–419, 1952.

[66] J. B. Tenenbaum, V. d. Silva, and J. C. Langford, *A global geometric framework for nonlinear dimensionality reduction*, science, vol. 290, no. 5500, pp. 2319–2323, 2000.

[67] M. C. Hout, M. H. Papesh, and S. D. Goldinger, *Multidimensional scaling*, Wiley Interdisciplinary Reviews: Cognitive Science, vol. 4, no. 1, pp. 93–103, 2013.

[68] F. Wang and J. Sun, *Survey on distance metric learning and dimensionality reduction in data mining*, Data mining and knowledge discovery, vol. 29, no. 2, pp. 534–564, 2015.

[69] Y. Hong, Q. Li, J. Jiang, and Z. Tu, *Learning a mixture of sparse distance metrics for classification and dimensionality reduction*, 2011 International Conference on Computer Vision, pp. 906–913, 2011.
[70] L. Liberti, *Distance geometry and data science*, Top, vol. 28, no. 2, pp. 271–339, 2020.

[71] N. M. Freris, S. R. Graham, and P. R. Kumar, *Fundamental Limits on Synchro- nizing Clocks Over Networks*, IEEE Transactions on Automatic Control, vol. 56, no. 6, pp. 1352–1364, 2011.

[72] P. Veríssimo and M. Raynal, *Time in Distributed System Models and Algorithms*, Advances in Distributed Systems: Advanced Distributed Computing: From Algo- rithms to Systems, S. Krakowiak and S. Shrivastava, Eds., 2000.

[73] A. Bahr, J. J. Leo nard, and M. F. Fallon, *Cooperative localization for autonomous underwater vehicles*, The International Journal of Robotics Research, vol. 28, no. 6, pp. 714–728, 2009.

[74] Q. Chen, K. You, and S. Song, *Cooperative localization for autonomous underwater vehicles using parallel projection*, 2017 13th IEEE International Conference on Control & Automation (ICCA), pp. 788–793, 2017.

[75] E. D. Demaine et al., *The Distance Geometry of Music*, Computational geometry, vol. 42, no. 5, pp. 429–454, 2009.

[76] F. Beck, M. Burch, S. Diehl, and D. Weiskopf, *A taxonomy and survey of dynamic graph visualization*, Computer graphics forum, vol. 36, no. 1, pp. 133–159, 2017.

[77] I. Herman, G. Melançon, and M. S. Marshall, *Graph visualization and navigation in information visualization: a survey*, IEEE Transactions on visualization and computer graphics, vol. 6, no. 1, pp. 24–43, 2000.

[78] R. de Freitas, B. Dias, N. Maculan, and J. Szwartfiter, *Distance geometry approach for special graph coloring problems*, arXiv preprint arXiv:1606.04978, 2016.

[79] I. J. Schoenberg, *Remarks to maurice frechet’s article "sur la definition axiomatique d’une classe d’espace distances vectoriellement applicable sur l’espace de hilbert"*, Annals of Mathematics, pp. 724–732, 1935.

[80] K. Pearson, *On lines and planes of closest fit to systems of points in space*, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, vol. 2, pp. 559–572, 1901.

[81] A. E. García, *Large-amplitude nonlinear motions in proteins*, Phys. Rev. Lett., vol. 68, pp. 2696–2699, 1992.
[82] R. H. Keshavan, A. Montanari, and S. Oh, *Matrix Completion from a Few Entries*, IEEE transactions on information theory, vol. 56, pp. 2980–2998, 2010.

[83] P. Jain, P. Netrapalli, and S. Sanghavi, *Low-rank matrix completion using alternating minimization*, Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 665–674, 2013.

[84] R. Reams, G. Chatham, W. Glunt, D. McDonald, and T. Hayden, *Determining protein structure using the distance geometry program apa*, Computers & Chemistry, vol. 23, no. 2, pp. 153–163, 1999.

[85] L. Grippo and M. Sciandrone, *On the convergence of the block nonlinear gauss-seidel method under convex constraints*, Operations research letters, vol. 26, no. 3, pp. 127–136, 2000.

[86] M. J. Sippl and H. A. Scheraga, *Solution of the embedding problem and decomposition of symmetric matrices*, Proceedings of the National Academy of Sciences, vol. 82, no. 8, pp. 2197–2201, 1985.

[87] N. Krislock and H. Wolkowicz, *Explicit sensor network localization using semidefinite representations and facial reductions*, SIAM Journal on Optimization, vol. 20, no. 5, pp. 2679–2708, 2010.

[88] H. Shi and Q. Li, *A facial reduction approach for the single source localization problem*, Journal of Global Optimization, pp. 1–25, 2022.

[89] D. K. Agrafiotis, *Stochastic Proximity Embedding*, Journal of computational chemistry, vol. 24, no. 10, pp. 1215–1221, 2003.

[90] B. Hendrickson, *The molecule problem: exploiting structure in global optimization*, SIAM Journal on Optimization, vol. 5, no. 4, pp. 835–857, 1995.

[91] P. Biswas, K.-C. Toh, and Y. Ye, *A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation*, SIAM Journal on Scientific Computing, vol. 30, no. 3, pp. 1251–1277, 2008.

[92] P. Biswas and Y. Ye, *Semidefinite programming for ad hoc wireless sensor network localization*, pp. 46–54, 2004.

[93] M. Cucuringu, A. Singer, and D. Cowburn, *Eigenvector synchronization, graph rigidity and the molecule problem*, Information and Inference: A Journal of the IMA, vol. 1, no. 1, pp. 21–67, 2012.
[94] C. Lavor, L. Liberti, and N. Maculan, *Computational experience with the molecular distance geometry problem*, Global optimization: scientific and engineering case studies, pp. 213–225, 2006.

[95] L. T. Hoai An, *Solving large scale molecular Distance Geometry Problems by a smoothing technique via the Gaussian transform and D.C. programming*, Journal of Global Optimization, vol. 27, no. 4, pp. 375–397, 2003.

[96] L. T. H. An and P. D. Tao, *Large-scale molecular optimization from distance matrices by D.C. optimization approach*, SIAM Journal on Optimization, vol. 14, no. 1, pp. 77–114, 2003.

[97] L. Liberti, C. Lavor, N. Maculan, and F. Marinelli, *Double variable neighbourhood search with smoothing for the molecular distance geometry problem*, Journal of Global Optimization, vol. 43, pp. 207–218, 2009.

[98] G. A. Williams, J. M. Dugan, and R. B. Altman, *Constrained global optimization for estimating molecular structure from atomic distances*, Journal of computational biology, vol. 8, no. 5, pp. 523–547, 2001.

[99] M. Souza, A. E. Xavier, C. Lavor, and N. Maculan, *Hyperbolic smoothing and penalty techniques applied to molecular structure determination*, Operations Research Letters, vol. 39, no. 6, pp. 461–465, 2011.

[100] S. Kucherenko and Y. Sytsko, *Application of deterministic low-discrepancy sequences in global optimization*, Computational Optimization and Applications, vol. 30, pp. 297–318, 2005.

[101] L. Liberti and M. Drazic, *Variable neighbourhood search for the global optimization of constrained NLPs*, Proceedings of GO Workshop, Almeria, Spain, vol. 2005, 2005.

[102] A. Grosso, M. Locatelli, and F. Schoen, *Solving molecular distance geometry problems by global optimization algorithms*, Computational Optimization and Applications, vol. 43, pp. 23–37, 2009.

[103] D. J. Wales and J. P. Doye, *Global optimization by basin-hopping and the lowest energy structures of lennard-jones clusters containing up to 110 atoms*, The Journal of Physical Chemistry A, vol. 101, no. 28, pp. 5111–5116, 1997.
[104] D. S. Gonçalves and A. Mucherino, *A distance geometry procedure using the Levenberg-Marquardt algorithm and with applications in biology but not only*, International Work-Conference on Bioinformatics and Biomedical Engineering, pp. 142–152, 2022.

[105] A. Mucherino, D. Gonçalves, A. Bernardin, L. Hoyet, and F. Multon, *A Distance-Based Approach for Human Posture Simulations*, 12th Conference on Computer Science and Intelligence Systems (FedCSIS17), pp. 441–444, 2017.

[106] A. Bernardin, L. Hoyet, A. Mucherino, D. Gonçalves, and F. Multon, *Normalized Euclidean Distance Matrices for Human Motion Retargeting*, Proceedings of the 10th journal Conference on Motion in Games (MIG ’17), 2017.

[107] I. Goodfellow, Y. Bengio, and A. Courville, *Deep learning*. 2016.

[108] S. Ruder, *An overview of gradient descent optimization algorithms*, arXiv preprint arXiv:1609.04747, 2016.

[109] Q. V. Le, J. Ngiam, A. Coates, A. Lahiri, B. Prochnow, and A. Y. Ng, *On optimization methods for deep learning*, Proceedings of the 28th international conference on international conference on machine learning, pp. 265–272, 2011.

[110] S.-i. Amari, *Backpropagation and stochastic gradient descent method*, Neurocomputing, vol. 5, no. 4-5, pp. 185–196, 1993.

[111] E. G. Birgin, J. M. Martínez, and M. Raydan, *Spectral projected gradient methods: review and perspectives*, Journal of Statistical Software, vol. 60, pp. 1–21, 2014.

[112] L. Grippo, F. Lampariello, and S. Lucidi, *A nonmonotone line search technique for Newton's method*, SIAM journal on Numerical Analysis, vol. 23, pp. 707–716, 1986.

[113] H. Zhang and W. W. Hager, *A nonmonotone line search technique and its application to unconstrained optimization*, SIAM journal on Optimization, vol. 14, pp. 1043–1056, 2004.

[114] J. Barzilai and J. M. Borwein, *Two-point step size gradient methods*, IMA journal of numerical analysis, vol. 8, pp. 141–148, 1988.

[115] E. G. Birgin, J. M. Martínez, and M. Raydan, *Nonmonotone spectral projected gradient methods on convex sets*, SIAM Journal on Optimization, vol. 10, no. 4, pp. 1196–1211, 2000.
[116] Q. Dong and Z. Wu, *A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances*, Journal of Global Optimization, vol. 22, pp. 365–375, 2002.

[117] Q. Dong and Z. Wu, *A Geometric Build-up Algorithm for Solving the Molecular Distance Geometry Problem with Sparse Distance data*, Journal of Global Optimization, vol. 26, pp. 321–333, 2003.

[118] D. Wu and Z. Wu, *An Updated Geometric Build-up Algorithm for Solving the Molecular Distance Geometry Problems with Sparse Distance data*, Journal of Global Optimization, vol. 37, pp. 661–673, 2007.

[119] R. dos Santos Carvalho, C. Lavor, and F. Protti, *Extending the geometric build-up algorithm for the molecular distance geometry problem*, Information Processing Letters, vol. 108, no. 4, pp. 234–237, 2008.

[120] Cplex IBM ILOG, *V12. 1: User's Manual for CPLEX*, International Business Machines Corporation, vol. 46, no. 53, p. 157, 2009.

[121] R. L. Burden, J. D. Faires, and A. M. Burden, *Numerical analysis*. 2015.

[122] C. Lavor, J. Lee, A. Lee-St.John, L. Liberti, A. Mucherino, and M. Sviridenko, *Discretization orders for distance geometry problems*, Optimization Letters, vol. 6, pp. 783–796, 2012.

[123] A. Cassioli, O. Günlük, C. Lavor, and L. Liberti, *Discretization vertex orders in distance geometry*, Discrete Applied Mathematics, vol. 197, pp. 27–41, 2015.

[124] J. Omer and A. Mucherino, *The referenced vertex ordering problem: theory, applications, and solution methods*, Open Journal of Mathematical Optimization, vol. 2, pp. 1–29, 2021.

[125] L. Liberti, B. Masson, J. Lee, C. Lavor, and A. Mucherino, *On the number of realizations of certain Henneberg graphs arising in protein conformation*, Discrete Applied Mathematics, vol. 165, pp. 213–232, 2014.

[126] A. Mucherino, C. Lavor, T. Malliavin, L. Liberti, M. Nilges, and N. Maculan, *Influence of pruning devices on the solution of molecular distance geometry problems*, Experimental Algorithms: 10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5-7, 2011. Proceedings 10, pp. 206–217, 2011.

[127] B. Worley et al., *Tuning interval Branch-and-Prune for protein structure determination*, Journal of Global Optimization, vol. 72, pp. 109–127, 2018.
[128] T. E. Malliavin, A. Mucherino, C. Lavor, and L. Liberti, *Systematic exploration of protein conformational space using a distance geometry approach*, Journal of Chemical Information and Modeling, vol. 59, no. 10, pp. 4486–4503, 2019.

[129] C. Lavor, R. Alves, W. Figueiredo, A. Petraglia, and N. Maculan, *Clifford algebra and the discretizable molecular distance geometry problem*, Advances in Applied Clifford Algebras, vol. 25, pp. 925–942, 2015.

[130] D. S. Gonçalves and A. Mucherino, *Discretization orders and efficient computation of cartesian coordinates for distance geometry*, Optimization Letters, vol. 8, pp. 2111–2125, 2014.

[131] I. Coope, *Reliable computation of the points of intersection of n spheres in Rⁿ*, ANZIAM Journal, vol. 42, pp. C461–C477, 2000.

[132] J. Parsons, J. B. Holmes, J. M. Rojas, J. Tsai, and C. E. Strauss, *Practical conversion from torsion space to cartesian space for in silico protein synthesis*, Journal of computational chemistry, vol. 26, no. 10, pp. 1063–1068, 2005.

[133] J. K. Leman et al., *Macromolecular modeling and design in rosetta: recent methods and frameworks*, Nature methods, vol. 17, no. 7, pp. 665–680, 2020.

[134] S. B. Hengeveld, M. Merabti, F. Pascale, and T. E. Malliavin, *A Study on the Covalent Geometry of Proteins and Its Impact on Distance Geometry*, International Conference on Geometric Science of Information, pp. 520–530, 2023.

[135] Z. Wang et al., *Total body protein: a new cellular level mass and distribution prediction model*, The American Journal of Clinical Nutrition, vol. 78, no. 5, pp. 979–984, 2003.

[136] R. Dosi, A. Carusone, A. Chambery, V. Severino, A. Parente, and A. Di Maro, *Rapid primary structure determination of myoglobins by a complementary approach based on mass spectrometry and edman degradation*, Food chemistry, vol. 133, no. 4, pp. 1646–1652, 2012.

[137] J. B. Smith, *Peptide sequencing by edman degradation*, eLS, 2001.

[138] H. D. Niall, *Automated edman degradation: the protein sequenator*, Methods in enzymology, vol. 27, pp. 942–1010, 1973.

[139] K. Biemann, *Contributions of mass spectrometry to peptide and protein structure*, Biomedical & environmental mass spectrometry, vol. 16, no. 1-12, pp. 99–111, 1988.
[140] R. Zubarev, *Protein primary structure using orthogonal fragmentation techniques in fourier transform mass spectrometry*, Expert review of proteomics, vol. 3, no. 2, pp. 251–261, 2006.

[141] B. T. Chait, *Chemistry: mass spectrometry: bottom-up or*, Neuroscience, vol. 123, p. 931, 2004.

[142] J. A. Maier, C. Martinez, K. Kasavajhala, L. Wickstrom, K. E. Hauser, and C. Simmerling, *Ff14sb: improving the accuracy of protein side chain and backbone parameters from ff99sb*, Journal of Chemical Theory and Computation, vol. 11, pp. 3696–3713, 2015.

[143] A. Liwo, J. Lee, D. R. Ripoll, J. Pillardy, and H. A. Scheraga, *Protein structure prediction by global optimization of a potential energy function*, Proceedings of the National Academy of Sciences, vol. 96, no. 10, pp. 5482–5485, 1999.

[144] M. J. Dudek, K. Ramnarayan, and J. W. Ponder, *Protein structure prediction using a combination of sequence homology and global energy minimization: ii. energy functions*, Journal of Computational Chemistry, vol. 19, no. 5, pp. 548–573, 1998.

[145] B. Matthews, *X-ray crystallographic studies of proteins*, Annual review of physical chemistry, vol. 27, no. 1, pp. 493–493, 1976.

[146] M. Woolfson, *An Introduction to X-ray Crystallography* (An Introduction to X-ray Crystallography). 1997.

[147] M. Smyth and J. Martin, *X Ray crystallography*, Molecular Pathology, vol. 53, no. 1, p. 8, 2000.

[148] A. Ilari and C. Savino, *Protein structure determination by X-ray crystallography*, Bioinformatics: Data, Sequence Analysis and Evolution, pp. 63–87, 2008.

[149] M. Benvenuti and S. Mangani, *Crystallization of soluble proteins in vapor diffusion for x-ray crystallography*, Nature protocols, vol. 2, no. 7, pp. 1633–1651, 2007.

[150] S. H. Chung, D. L. Ma, and R. D. Braatz, *Optimal seeding in batch crystallization*, The Canadian journal of chemical engineering, vol. 77, no. 3, pp. 590–596, 1999.

[151] A. Srivastava, T. Nagai, A. Srivastava, O. Miyashita, and F. Tama, *Role of computational methods in going beyond x-ray crystallography to explore protein structure and dynamics*, International journal of molecular sciences, vol. 19, no. 11, p. 3401, 2018.
[152] Y. Cheng, N. Grigorieff, P. A. Penczek, and T. Walz, *A primer to single-particle cryo-electron microscopy*, Cell, vol. 161, no. 3, pp. 438–449, 2015.

[153] K. R. Vinothkumar and R. Henderson, *Single particle electron cryomicroscopy: trends, issues and future perspective*, Quarterly reviews of biophysics, vol. 49, e13, 2016.

[154] D. J. Mills, *Setting up and operating a cryo-em laboratory*, Quarterly Reviews of Biophysics, vol. 54, e2, 2021.

[155] E. Palovcak et al., *A simple and robust procedure for preparing graphene-oxide cryo-EM grids*, Journal of structural biology, vol. 204, no. 1, pp. 80–84, 2018.

[156] G. Weissenberger, R. J. Henderikx, and P. J. Peters, *Understanding the invisible hands of sample preparation for cryo-EM*, Nature Methods, vol. 18, no. 5, pp. 463–471, 2021.

[157] X. Zhang et al., *Near-atomic resolution using electron cryomicroscopy and single-particle reconstruction*, Proceedings of the National Academy of Sciences, vol. 105, no. 6, pp. 1867–1872, 2008.

[158] A. Punjani, H. Zhang, and D. J. Fleet, *Non-uniform refinement: adaptive regularization improves single-particle cryo-em reconstruction*, Nature methods, vol. 17, no. 12, pp. 1214–1221, 2020.

[159] A. Ben-Shem, N. Garreau de Loubresse, S. Melnikov, L. Jenner, G. Yusupova, and M. Yusupov, *The structure of the eukaryotic ribosome at 3.0 Å resolution*, Science, vol. 334, no. 6062, pp. 1524–1529, 2011.

[160] S. Safarian et al., *Active site rearrangement and structural divergence in prokaryotic respiratory oxidases*, Science, vol. 366, no. 6461, pp. 100–104, 2019.

[161] E. D'Imprima and W. Kühlbrandt, *Current limitations to high-resolution structure determination by single-particle cryoem*, Quarterly Reviews of Biophysics, vol. 54, e4, 2021.

[162] P. Koukos and A. Bonvin, *Integrative modelling of biomolecular complexes*, Journal of molecular biology, vol. 432, no. 9, pp. 2861–2881, 2020.

[163] R. Puthenveetil and O. Vinogradova, *Solution nmr: a powerful tool for structural and functional studies of membrane proteins in reconstituted environments*, Journal of Biological Chemistry, vol. 294, no. 44, pp. 15914–15931, 2019.
[164] R. R. Ernst, G. Bodenhausen, and A. Wokaun, *Principles of nuclear magnetic resonance in one and two dimensions*, 1987.

[165] D. Neuhaus, *Nuclear overhauser effect*, eMagRes, 2007.

[166] P. J. Van Laarhoven, E. H. Aarts, P. J. van Laarhoven, and E. H. Aarts, *Simulated annealing*. 1987.

[167] D. Bertsimas and J. Tsitsiklis, *Simulated annealing*, Statistical science, vol. 8, no. 1, pp. 10–15, 1993.

[168] O. Sannikov, E. Ye, B. M. Pinto, P. Saunders, and N. Merbouh, *Introducing complex nmr mixtures at the undergraduate level: isomerization, separation and analysis of the diels-alder adducts from the reaction of methylcyclopentadiene and maleic anhydride (part ii)*, Journal of Laboratory Chemical Education, vol. 8, no. 3, pp. 39–80, 2020.

[169] J. Jumper et al., *Highly accurate protein structure prediction with alphafold*, Nature, vol. 596, no. 7873, pp. 583–589, 2021.

[170] M. AlQuraishi, *Machine learning in protein structure prediction*, Current opinion in chemical biology, vol. 65, pp. 1–8, 2021.

[171] *Algorithms for Structure Comparison and Analysis: Homology Modelling of Proteins*, Encyclopedia of Bioinformatics and Computational Biology, S. Ranganathan, M. Gribskov, K. Nakai, and C. Schönbach, Eds., pp. 38–61, 2019.

[172] D. T. Jones, T. Singh, T. Kosciolek, and S. Tetchner, *Metapsicov: combining coevolution methods for accurate prediction of contacts and long range hydrogen bonding in proteins*, Bioinformatics, vol. 31, no. 7, pp. 999–1006, 2015.

[173] S. Wang, S. Sun, Z. Li, R. Zhang, and J. Xu, *Accurate de novo prediction of protein contact map by ultra-deep learning model*, PLoS computational biology, vol. 13, no. 1, e1005324, 2017.

[174] V. Golkov et al., *Protein contact prediction from amino acid co-evolution using convolutional networks for graph-valued images*, Advances in Neural Information Processing Systems, vol. 29, 2016.

[175] A. W. Senior et al., *Improved protein structure prediction using potentials from deep learning*, Nature, vol. 577, no. 7792, pp. 706–710, 2020.
[176] J. Xu, *Distance-based protein folding powered by deep learning*, Proceedings of the National Academy of Sciences, vol. 116, no. 34, pp. 16856–16865, 2019.

[177] M. AlQuraishi, *End-to-end differentiable learning of protein structure*, Cell systems, vol. 8, no. 4, pp. 292–301, 2019.

[178] A. v. Bondi, *Van der waals volumes and radii*, The Journal of physical chemistry, vol. 68, no. 3, pp. 441–451, 1964.

[179] B. Brooks, R. Bruccoleri, B. Olafson, D. States, S. Swaminathan, and M. Karplus, *Charmm: a program for macromolecular energy, minimization, and dynamics calculations*, Journal of Computational Chemistry, vol. 4, pp. 187–217, 2004.

[180] R. Engh and R. Huber, *Accurate bond and angle parameters for X-ray protein structure refinement*, Acta Crystallogr A, vol. 47, pp. 392–400, 1991.

[181] S. B. Hengeveld, T. E. Malliavin, L. Liberti, and A. Mucherino, *Collecting Data for Generating Distance Geometry Graphs for Protein Structure Determination*, Proceedings of Roadaf23, 2023.

[182] K. Wuthrich, *NMR in Structural Biology: A Collection of Papers by Kurt Wüthrich*. World Scientific, 1995, vol. 5.

[183] Y. Shen and A. Bax, *Protein structural information derived from NMR chemical shift with the neural network program TALOS-N*, Methods Mol Biol, vol. 1260, pp. 17–32, 2015.

[184] L. Zhang, H. Ma, W. Qian, and H. Li, *Protein structure optimization using improved simulated annealing algorithm on a three-dimensional ab off-lattice model*, Computational Biology and Chemistry, vol. 85, p. 107237, 2020.

[185] C. D. Schwieters, J. J. Kuszewski, N. Tjandra, and G. M. Clore, *The xplor-nih nmr molecular structure determination package*, Journal of magnetic resonance, vol. 160, no. 1, pp. 65–73, 2003.

[186] P. Güntert, *Automated nmr structure calculation with cyana*, Protein NMR techniques, pp. 353–378, 2004.

[187] M. Berjanskii et al., *Genmr: a web server for rapid nmr-based protein structure determination*, Nucleic acids research, vol. 37, no. suppl_2, W670–W677, 2009.

[188] P. Güntert and L. Buchner, *Combined automated noe assignment and structure calculation with cyana*, Journal of biomolecular NMR, vol. 62, pp. 453–471, 2015.
[189] T. Sugiki, N. Kobayashi, and T. Fujiwara, *Modern technologies of solution nuclear magnetic resonance spectroscopy for three-dimensional structure determination of proteins open avenues for life scientists*, Computational and structural biotechnology journal, vol. 15, pp. 328–339, 2017.

[190] H. Berman *et al.*, *The Protein Data Bank*, Nucleic Acids Research, vol. 28, pp. 235–242, 2000.

[191] D. K. Agrafiotis, A. C. Gibbs, F. Zhu, S. Izrailev, and E. Martin, *Conformational sampling of bioactive molecules: a comparative study*, Journal of chemical information and modeling, vol. 47, no. 3, pp. 1067–1086, 2007.

[192] A. Mucherino, L. Liberti, C. Lavor, and N. Maculan, *Comparisons between an exact and a metaheuristic algorithm for the molecular distance geometry problem, in Proceedings of the 11th Annual conference on Genetic and evolutionary computation*, 2009, pp. 333–340.

[193] W. Kabsch, *A solution for the best rotation to relate two sets of vectors*, Acta Crystallographica Section A: Crystal Physics, Diffraction, Theoretical and General Crystallography, vol. 32, no. 5, pp. 922–923, 1976.

[194] G. Wang and R. L. Dunbrack, *PISCES: a protein sequence culling server*, Bioinformatics, vol. 19, pp. 1589–1591, 2003.

[195] G. N. Ramachandran, C. Ramakrishnan, and V. Sasisekharan, *Stereochemistry of polypeptide chain configurations*, J Mol Biol., vol. 7, pp. 95–99, 1963.

[196] S. Khalife, T. Malliavin, and L. Liberti, *Secondary structure assignment of proteins in the absence of sequence information*, Bioinformatics Advances, vol. 1, no. 1, vbab038, 2021.

[197] A. Richards and J. P. How, *Aircraft trajectory planning with collision avoidance using mixed integer linear programming*, Proceedings of the 2002 American Control Conference (IEEE Cat. No. CH37301), vol. 3, pp. 1936–1941, 2002.

[198] T. B. Moeslund, A. Hilton, and V. Krüger, *A survey of advances in vision-based human motion capture and analysis*, vol. 104, no. 2, pp. 90–126, 2006.

[199] M. Meredith, S. Maddock, *et al.*, *Motion capture file formats explained*, Department of Computer Science, University of Sheffield, vol. 211, pp. 241–244, 2001.

[200] M. Antonio, *Introducing the interaction distance in the context of distance geometry for human motions*, Chebyshevskii sbornik, vol. 20, no. 2 (70), pp. 273–283, 2019.
[201] J.-S. Monzani, P. Baerlocher, R. Boulic, and D. Thalmann, *Using an intermediate skeleton and inverse kinematics for motion retargeting*, Computer Graphics Forum, vol. 19, no. 3, pp. 11–19, 2000.

[202] C. Rocha, C. Tonetto, and A. Dias, *A comparison between the denavit–hartenberg and the screw-based methods used in kinematic modeling of robot manipulators*, Robotics and Computer-Integrated Manufacturing, vol. 27, no. 4, pp. 723–728, 2011.

[203] D. Botto and M. Gola, *Solution of the inverse kinematic problem of a robot manipulator with eulerian joints*, IFAC Proceedings Volumes, vol. 27, no. 14, pp. 375–379, 1994.

[204] D. A. Drexler, *Solution of the closed-loop inverse kinematics algorithm using the crank-nicolson method*, 2016 IEEE 14th International Symposium on Applied Machine Intelligence and Informatics (SAMI), pp. 351–356, 2016.

[205] D. Manocha and J. F. Canny, *Efficient inverse kinematics for general 6r manipulators*, IEEE transactions on robotics and automation, vol. 10, no. 5, pp. 648–657, 1994.

[206] F. Caccavale, B. Siciliano, and L. Villani, *The role of euler parameters in robot control*, Asian journal of control, vol. 1, no. 1, pp. 25–34, 1999.

[207] E. G. Hemingway and O. M. O'Reilly, *Perspectives on euler angle singularities, gimbal lock, and the orthogonality of applied forces and applied moments*, Multi-body system dynamics, vol. 44, pp. 31–56, 2018.

[208] J. Diebel et al., *Representing attitude: euler angles, unit quaternions, and rotation vectors*, Matrix, vol. 58, no. 15-16, pp. 1–35, 2006.

[209] G. G. Slabaugh, *Computing euler angles from a rotation matrix*, Retrieved on August, vol. 6, no. 2000, pp. 39–63, 1999.

[210] W. Maurel and D. Thalmann, *Human shoulder modeling including scapulo-thoracic constraint and joint sinus cones*, Computers & Graphics, vol. 24, no. 2, pp. 203–218, 2000.

[211] A. Wolodtschenko and T. Forner, *Prehistoric and early historic maps in europe: conception of cd-atlas*, E-perimetron, vol. 2, pp. 114–116, 2007.

[212] C. Rolland-May, *A Valuation Model of Subjective Spaces*, IFAC Proceedings Volumes, vol. 16, no. 13, pp. 375–380, 1983.
[213] S. Raveau, J. C. Muñoz, and L. de Grange, *A topological route choice model for metro*, Transportation Research Part A: Policy and Practice, vol. 45, pp. 138–147, 2011.

[214] S. B. Hengeveld, F. Plastria, A. Mucherino, and D. A. Pelta, *A linear program for points of interest relocation in adaptive maps*, International Conference on Geometric Science of Information, pp. 551–559, 2023.

[215] D. G. Luenberger, Y. Ye, *et al.*, *Linear and nonlinear programming*. 1984, vol. 2.

[216] M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, *Linear programming and network flows*. 2011.

[217] A. Mucherino, *Binmeta: a new java package for meta-heuristic searches*, International Conference on Large-Scale Scientific Computing, pp. 242–249, 2021.

[218] *Hamming distance*, in *Encyclopedia of Biometrics*, S. Z. Li and A. Jain, Eds. 2009, pp. 668–668.

[219] S. B. Hengeveld and A. Mucherino, *Variable Neighborhood Search in Hamming Space*, To appear in Lecture Notes in Computer Science, Proceedings of the 14th International Conference on Large-Scale Scientific Computations (LSSC23), 2023.

[220] D. S. Goncalves, C. Lavor, L. Liberti, and M. Souza, *A new algorithm for the k-dmdgp subclass of distance geometry problems with exact distances*, Algorithmica, vol. 83, no. 8, pp. 2400–2426, 2021.

[221] N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, *Optical solution for bounded NP-complete problems*, Applied Optics, vol. 46, no. 5, pp. 711–724, 2007.

[222] M. Oltean and O. Muntean, *Solving the subset-sum problem with a light-based device*, Natural Computing, vol. 8, no. 2, pp. 321–331, 2009.

[223] X.-Y. Xu *et al.*, *A scalable photonic computer solving the subset sum problem*, Science Advances, vol. 6, no. 5, 2020.

[224] T. Haist and W. Osten, *An Optical Solution For The Traveling Salesman Problem*, Optics Express, vol. 15, no. 16, pp. 10473–10482, 2007.
<figure><img src="image_52.png" /></figure>
<figure><img src="image_53.png" /></figure>
**Titre** : Méthodes de géométrie d'extension des distances : pas seulement les distances (Une étude de trois applications, avec un focus sur la biologie structurale)

**Mot clés** : Géométrie des distances, Problème de Géométrie des Distances, Détermination de la Structure des Protéines, Repliement des Protéines, Discrétisation, Reciblage des Mouvements, Programmation Linéaire, Cartes Adaptatives

**Résumé** : Dans cette thèse, nous étudions différents aspects du Distance Geometry Problem (DGP). Le DGP est un problème inverse dans lequel un ensemble de distances par paire est inversé pour trouver une structure dans un espace euclidien, étant donné une certaine dimension $K$. Nous nous concentrons principalement sur l'application de la biologie structurelle, où nous pouvons exploiter les distances inter-atomiques pour calculer les structures des protéines. Pour cette application, nous sommes en mesure de discrétiser l'espace de recherche à l'aide de méthodes de branchement et de découpage. Nous étendons la méthode pour utiliser non seulement

les informations de distance, mais aussi les angles de torsion. Nous présentons des expériences utilisant des données NMR réelles avec des résultats prometteurs. Ensuite, nous nous penchons sur la géométrie dynamique des distances en nous concentrant sur les mouvements humains, jetant ainsi les bases de futurs projets qui pourraient se concentrer sur la modélisation de la dynamique des protéines. En outre, nous discutons des cartes adaptatives, qui sont un autre exemple d'application de la DG dans laquelle nous pouvons exploiter plus que les informations de distance. Enfin, nous terminons par un bref résumé et une description des travaux en cours.

**Title:** Extending Distance Geometry methods: not only distances (A study of three applications, with a focus on structural biology)

**Keywords:** Distance Geometry, Distance Geometry Problem, Protein Structure Determination, Protein Folding, Discretization, Motion Retargeting, Linear Programming, Adaptive maps.

**Abstract:** In this thesis, we study different aspects of the Distance Geometry Problem (DGP). The DGP is an inverse problem where a set of pairwise distances is inverted to find a structure in a Euclidean space, given a certain dimension $K$. Our main focus lies on the application of structural biology, where we can exploit inter-atomic distances to compute protein structures. For this application, we are able to discretize the search space using branch-and-prune methods. We extend the method to not only use distance information, but also

torsion angles. We present experiments using real NMR data with promising results. Next, we look at dynamical Distance Geometry with a main focus on human motions, laying the groundwork for future projects which could focus on modelling protein dynamics. Furthermore, we discuss adaptive maps, which is another example of an application of DG in which we can exploit more than just distance information. Finally, we end with a short summary of the thesis and a description of some ongoing work.