1000/1000
Hot
Most Recent
The distance geometry problem is that of characterization and study of sets of points based only on given values of the distances between member pairs. Therefore distance geometry has immediate relevance where distance values are determined or considered, such as biology, sensor network, surveying, cartography, and physics.
The distance geometry problem (DGP) is that of finding the coordinates of a set of points by using the distances between some pairs of such points.^{[1]} There exists nowadays a large community that is actively working on this problem, because there are several real-life applications that can lead to the formulation of a DGP. As an example, an interesting application is that of locating sensors in telecommunication networks.^{[2]} In such a case, the positions of some sensors are known (which are called anchors) and some of the distances between sensors (which can be anchors or not) are also known: the problem is to identify the positions in space for all sensors.
An interesting application arises in biology.^{[3]}^{[4]} Experimental techniques are able to estimate distances between pairs of atoms of a given molecule, and the problem becomes the one of identifying the three-dimensional conformation of the molecule, i.e. the positions of all its atoms. In this field, the main interest is on proteins, because discovering their three-dimensional conformation allows us to get clues about the function they are able to perform. The implications in related fields, such as biomedicine and drug design, are evident. When dealing with biological molecules, the DGP is generally referred to as molecular DGP (MDGP).
In the following, even if the article considers in general the DGP, the MDGP will be used as an example.
A straight line is the shortest path between two points. Therefore the distance from A to B is no bigger than the length of the straight-line path from A to C plus the length of the straight-line path from C to B. This fact is called the triangle inequality. If that sum happens to be equal to the distance from A to B, then the three points A, B, and C lie on a straight line, with C between A and B.
Similarly, suppose one knows
Knowing only these six numbers, one would like to figure out
Distance geometry includes the solution of such problems.
Of particular utility and importance are classifications by means of Cayley–Menger determinants, named after Arthur Cayley and Karl Menger:
The DGP is, by definition, a constraint satisfaction problem. It is however generally reformulated as an optimization problem in a continuous space, and its solution is then attempted by using techniques for global optimization (see for example ^{[5]}).
Under certain assumptions, however, the problem can be discretized, in the sense that the search domain of the optimization problem can be reduced to a discrete domain. When all distances are supposed to be exact (no experimental errors), the search domain becomes a binary tree, where the candidate positions for the same atom of the molecule are given on a common layer of the tree.^{[6]}^{[7]} The discretization allows us to enumerate the entire solution set (this is not possible in general when using global optimization methods).
The discretization assumptions^{[8]} are strongly based on the order in which the atoms of the molecule are considered. When considering the atoms of the molecule in their natural ordering, such assumptions are generally not satisfied. An interesting and fundamental pre-processing step for the discretization of DGPs is, therefore, the problem of identifying an order for the atoms that allows for the discretization. This problem can be solved in polynomial time, when all distances are supposed to be exact, as well as when some available distance is represented by a suitable interval.^{[9]}
Crippen and Havel are two pioneers of DGP, and they co-authored the book "Distance Geometry and Molecular Conformation",^{[3]} 1988. Much more recently, an edited book, collecting the most recent efforts from the scientific community for solving the DGP, was published by Springer.^{[1]} See this web page for the list of contributions.
Various conferences and workshops are held every year, where the focus is on DGP-related topics. However, the very first workshop completely devoted to DGP and its applications was held in 2013 in Manaus, Brazil: DGA13.