Distance-geometry embedding

A distance geometry calculation consists of two major parts. In the first, the distances are checked for consistency, using a set of inequalities that distances have to satisfy (this part is called bound smoothing ) in the second, distances are chosen randomly within these bounds, and the so-called metric matrix (Mij) is calculated. Embedding then converts this matrix to three-dimensional coordinates, using methods akin to principal component analysis [40]. 

Note that although the bounds on the distances satisfy the triangle inequalities, particular choices of distances between these bounds will in general violate them. Therefore, if all distances are chosen within their bounds independently of each other (the method that is used in most applications of distance geometry for NMR strucmre determination), the final distance matrix will contain many violations of the triangle inequalities. The main consequence is a very limited sampling of the conformational space of the embedded structures for very sparse data sets [48,50,51] despite the intrinsic randomness of the tech-... 

The simplest formulation of the packing problem is to give some collection of distance constraints and to calculate these coordinates in ordinary three-dimensional Euclidean space for the atoms of a molecule. This embedding problem - the Fundamental Problem of Distance Geometry - has been proven to be NP-hard [116]. However, this does not mean that practical algorithms for its solution do not exist [117-119]. 

The basic principles of the distance geometry approach have been described in Sec. 3.4. There, it was mentioned that the embedding procedure can produce several molecular geometries that do not violate the preset distance restrictions. Therefore, distance geometry per se can be regarded as a conformational search method. 

The procedure of DG calculations can be subdivided in three separated steps [119-121]. At first, holonomic matrices (see below for explanahon) with pairwise distance upper and lower limits are generated from the topology of the molecule of interest. These limits can be further restrained by NOE-derived distance information which are obtained from NMR experiments. In a second step, random distances within the upper and lower limit are selected and are stored in a metric matrix. This operation is called metrization. Finally, all distances are converted into a complex geometry by mathematical operations. Hereby, the matrix-based distance space is projected into a Gartesian coordinate space (embedding). 

---