Distance geometry - AbsoluteAstronomy.com

Distance geometry is the characterization

Characterization (mathematics)

In mathematics, the statement that "Property P characterizes object X" means, not simply that X has property P, but that X is the only thing that has property P. It is also common to find statements such as "Property Q characterises Y up to isomorphism". The first type of statement says in...

and study of sets of points based only on given values of the distance

Distance

Distance is a numerical description of how far apart objects are. In physics or everyday discussion, distance may refer to a physical length, or an estimation based on other criteria . In mathematics, a distance function or metric is a generalization of the concept of physical distance...

s between member pairs. Therefore distance geometry has immediate relevance where distance values are determined or considered, such as in surveying

Surveying

See Also: Public Land Survey SystemSurveying or land surveying is the technique, profession, and science of accurately determining the terrestrial or three-dimensional position of points and the distances and angles between them...

, cartography

Cartography

Cartography is the study and practice of making maps. Combining science, aesthetics, and technique, cartography builds on the premise that reality can be modeled in ways that communicate spatial information effectively.The fundamental problems of traditional cartography are to:*Set the map's...

and physics

Physics

Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...

Introduction

The Distance Geometry Problem (DGP) is the problem of finding the coordinates of a set of points starting from the distances between pairs of such points,,. Such a problem is nowadays much studied by the scientific community, because there are real-life applications that lead to the formulation of a DGP. As an example, an interesting application is the problem of locating sensors in telecommunication networks. 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 known: the problem is to locate the positions of all the sensors.

Many other real-life applications that can be formulated as DGPs arise in biology and chemistry. For example, some models for protein predictions are based on a DGP, and also some models for protein docking. However, in this field, the most studied problem is the following. The coordinates of the atoms of a given molecular conformation are to be discovered by exploiting only some of the distances between pairs of atoms found by experimental techniques. If this is the case, the problem is known in the literature as the Molecular Distance Geometry Problem (MDGP).

Discussion

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

Triangle inequality

In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....

. 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

the distance from A to B;
the distance from A to C;
the distance from A to D;
the distance from B to C;
the distance from B to D; and
the distance from C to D.

Knowing only these six numbers, one would like to figure out

whether A, B, C, and D lie on a common straight line;
whether A, B, and C lie on a common line but D is not on that line (and similarly for any of A, B, and C in the role of the one exceptional point);
whether all four points lie in a common plane;
if they lie in a common plane, whether one of them is in the interior of the triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....

formed by the other three, and if so, which one.

Distance geometry includes the solution of such problems.

Cayley–Menger determinants

Of particular utility and importance are classifications by means of Cayley–Menger determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

s, named after Arthur Cayley

Arthur Cayley

Arthur Cayley F.R.S. was a British mathematician. He helped found the modern British school of pure mathematics....

and Karl Menger

Karl Menger

Karl Menger was a mathematician. He was the son of the famous economist Carl Menger. He is credited with Menger's theorem. He worked on mathematics of algebras, algebra of geometries, curve and dimension theory, etc...

a set Λ (with at least three distinct elements) is called straight iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...

, for any three elements A, B, and C of Λ,

a set Π (with at least four distinct elements) is called plane iff, for any four elements A, B, C and D of Π,

but not all triples of elements of Π are straight to each other;

a set Φ (with at least five distinct elements) is called flat iff, for any five elements A, B, C, D and E of Φ,

but not all quadruples of elements of Φ are plane to each other;

and so on.

Software for distance geometry

DGSOL. It is based on the idea of approximating the penalty function with a sequence of smoother functions converging to the original objective function. It is usually used for performing comparisons to other newly proposed techniques, whose code is often not released. DGSOL solves distance geometry problems where a lower and an upper bound on the distances are available.
MD-jeep. This software is based on a combinatorial reformulation of the distance geometry problem. A Branch & Prune algorithm is implemented for an efficient solution of the reformulated problem. It has been mainly applied to distance geometry problems related to protein molecules.
Xplor-NIH. It has been particularly designed for solving instances of the problem in which the data come from NMR experiments, and it includes different functionalities. In particular, for the solution of the distance geometry problems, it makes use of heuristic methods (such as Simulated Annealing) and local search methods (such as Conjugate Gradient Minimization).
TINKER. This is a package for molecular modeling and design. It includes many force fields for attempting the prediction of protein conformations from their chemical structure only. One of its functionalities, however, is to solve distance geometry problems.

Introduction

Discussion

Cayley–Menger determinants

Software for distance geometry

See also