Distance geometry problem

The distance geometry problem is the characterization and study of sets of points based only on given values of the distances between member pairs.[1][2][3] Therefore distance geometry has immediate relevance where distance values are determined or considered, such as biology,[4] sensor network,[5] surveying, cartography and physics.

Applications

The distance geometry problem (DGP) is the one of finding the coordinates of a set of points by using the distances between some pairs of such points.[3] 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 the one of locating sensors in telecommunication networks.[5] 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.[4][6] 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.

Basic issues

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.

Cayley–Menger determinants

Of particular utility and importance are classifications by means of Cayley–Menger determinants, named after Arthur Cayley and Karl Menger:

 \det \begin{bmatrix} 
       0 & d(AB)^2 & d(AC)^2 & 1 \\
 d(AB)^2 &    0    & d(BC)^2 & 1 \\
 d(AC)^2 & d(BC)^2 &       0 & 1 \\
       1 &       1 &       1 & 0
\end{bmatrix} = 0,
 \det \begin{bmatrix} 
       0 & d(AB)^2 & d(AC)^2 & d(AD)^2 & 1 \\
 d(AB)^2 &    0    & d(BC)^2 & d(BD)^2 & 1 \\
 d(AC)^2 & d(BC)^2 &       0 & d(CD)^2 & 1 \\
 d(AD)^2 & d(BD)^2 & d(CD)^2 &       0 & 1 \\
       1 &       1 &       1 & 1       & 0
\end{bmatrix} = 0,
but not all triples of elements of Π are straight to each other;
 \det \begin{bmatrix} 
       0 & d(AB)^2 & d(AC)^2 & d(AD)^2 & d(AE)^2 & 1 \\
 d(AB)^2 &    0    & d(BC)^2 & d(BD)^2 & d(BE)^2 & 1 \\
 d(AC)^2 & d(BC)^2 &       0 & d(CD)^2 & d(CE)^2 & 1 \\
 d(AD)^2 & d(BD)^2 & d(CD)^2 &       0 & d(DE)^2 & 1 \\
 d(AE)^2 & d(BE)^2 & d(CE)^2 & d(DE)^2 &       0 & 1 \\
       1 &       1 &       1 & 1       &       1 & 0
\end{bmatrix} = 0,
but not all quadruples of elements of Φ are plane to each other; and so on.

Discretization and orders

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 [7]).

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.[8][9] The discretization allows us to enumerate the entire solution set (this is not possible in general when using global optimization methods).

The discretization assumptions[2] 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.[10]

Software for distance geometry

Books and conferences

Crippen and Havel are two pioneers of DGP, and they co-authored the book "Distance Geometry and Molecular Conformation",[4] 1988. Much more recently, an edited book, collecting the most recent efforts from the scientific community for solving the DGP, was published by Springer.[3] 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.

See also

References

  1. Yemini, Y. (1978). "The positioning problem — a draft of an intermediate summary". Conference on Distributed Sensor Networks, Pittsburgh.
  2. 1 2 Liberti, L.; Lavor, C.; Maculan, N.; Mucherino, A. "Euclidean Distance Geometry and Applications". SIAM Review, to appear.
  3. 1 2 3 Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N. (2013). Distance Geometry: Theory, Methods and Applications.
  4. 1 2 3 Crippen, G.M.; Havel, T.F. (1988). "Distance Geometry and Molecular Conformation". John Wiley & Sons.
  5. 1 2 Biswas, P.; Lian, T.; Wang, T.; Ye, Y. (2006). "Semidefinite programming based algorithms for sensor network localization". ACM Transactions in Sensor Networks 2: 188–220. doi:10.1145/1149283.1149286.
  6. Blumenthal, L.M. (1970). Theory and applications of distance geometry (2nd ed.). Bronx, New York: Chelsea Publishing Company. p. 347. ISBN 0-8284-0242-6. LCCN 79113117.
  7. More, J.J.; Wu, Z. (1999). "Distance Geometry Optimization for Protein Structures". Journal of Global Optimization 15: 219–223.
  8. Liberti, L.; Lavor, C.; Maculan, N. (2008). "A Branch-and-Prune Algorithm for the Molecular Distance Geometry Problem". International Transactions in Operational Research 15: 1–17. doi:10.1111/j.1475-3995.2007.00622.x.
  9. Mucherino, A.; Liberti, L.; Lavor, C.; Maculan, N. (2009). "Comparisons between an Exact and a MetaHeuristic Algorithm for the Molecular Distance Geometry Problem". ACM Conference Proceedings, Genetic and Evolutionary Computation Conference (GECCO09): 333–340.
  10. Mucherino, A. (2013). "On the Identification of Discretization Orders for Distance Geometry with Intervals". Lecture Notes in Computer Science 8085: 231–238. doi:10.1007/978-3-642-40020-9_24.
This article is issued from Wikipedia - version of the Friday, October 02, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.