Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures (Q1730533)

In this review paper, the authors provide an update on the state of the art reviewed in their paper on the topic of assigned (aDGP) and unassigned (uDGP) distance geometry problems [4OR 14, No. 4, 337--376 (2016; Zbl 1364.51005)]. A summary of the definitions, notations and results is given. Moreover, they discuss various important advances that have emerged over the years 2016--2018, for example generalization of the mathematical description to a new class of problems called vector geometry problems (VGPs), which can be assigned (aVGP) or unassigned (uVGP). In the following, we formally state these problems. For this purpose, we need some additional definitions. Let \(V\) be a set of \(n\) objects and \(x : V \rightarrow \mathbb{R}^K\) be the function that assigns positions (coordinates) in a Euclidean space of dimension \(K\) to the objects belonging to the set \(V\), whose elements are called vertices. The function \(x\) is referred to as a \textit{realization}. Moreover, for any \(u,v \in V\), we denote its corresponding edge weight by \(d(u, v)\) or associated vector by \(\mathbf{s}(u, v)\). For DGP, let \(\mathcal{D} = (d_1, d_2, \ldots, d_m)\) be a finite sequence consisting of \(m\) distances, called a \textit{distance list}. Distances in \(\mathcal{D}\) can be represented either with a nonnegative real number (when the distance is exact) or by an interval. On the other hand, for VGP, let \(\mathcal{D}_s = (\pm \mathbf{s}_1, \pm \mathbf{s}_2, \ldots, \pm \mathbf{s}_m)\) be a finite sequence consisting of \(m\) interparticle vectors. Note that for every vector \(\mathbf{s}_i\) in the list, its negative \(-\mathbf{s}_i\) also appears. Let us denote the set of all possible unordered pairs \(\lbrace u, v \rbrace\) of vertices in \(V\) by \(\hat{E}\). Then an injective function \(\ell : \lbrace 1, 2, \ldots, m \rbrace \rightarrow \hat{E}\) is called \textit{assignment function}. Finally, we can define the corresponding problems. 1. Given a list \(\mathcal{D}\) of \(m\) distances, the unassigned distance geometry problem (uDGP) in dimension \(K\) asks to find an assignment function \(\ell\) and a realization \(x\) such that for any \(\lbrace u,v \rbrace \in \ell(\lbrace 1, 2, \ldots, m \rbrace)\) it holds \(d(u, v) = d_{\ell^{-1}}( \lbrace u, v \rbrace)\), \( \Vert x(u) - x(v) \Vert = d(u, v)\). 2. Given a weighted undirected graph \(G = (V, E, d)\), the assigned distance geometry problem (aDGP) in dimension \(K\) asks to find a realization \(x\) such that for any \(\lbrace u,v \rbrace \in E\) it holds \( \Vert x(u) - x(v) \Vert = d(u, v)\). 3. Given a list \(\mathcal{D}_s\) of \(m\) vector interpoint separations, the unassigned vector geometry problem (uVGP) in dimension \(K\) asks to find an assignment function \(\ell\) and a realization \(x\) such that for any \(\lbrace u,v \rbrace \in \ell(\lbrace 1, 2, \ldots, m \rbrace)\) it holds \(\mathbf{s}(u, v) = \mathbf{s}_{\ell^{-1}}( \lbrace u, v \rbrace)\), \( x(u) - x(v) = \mathbf{s}(u, v)\). 4. Given a weighted undirected graph \(G = (V, E, d)\), the assigned vector geometry problem (aVGP) in dimension \(K\) asks to find a realization \(x\) such that for any \(\lbrace u,v \rbrace \in E\) it holds \( x(u) - x(v) = \mathbf{s}(u, v)\). The authors focus particularly on methods that determine graph embeddings by iteratively growing substructures. Moreover, they present two main approaches to the DGP: the first approach (for the uDGP) is based on the concept of finding unique substructures during iterative growth of a final unique realization, and the second approach (for the aDGP) reduces the search space to a discrete one having the structure of a tree (discretizable distance geometry problem). Finally, some applications are also included: the identification of conformations of protein molecules and determining the nanostructures of complex materials.