The Distance Matrix

The distance matrix D of a graph G with n vertices is a square n x n symmetric matrix as represented by Eq. (13), where is the distance between the vertices Vi and Vj in the graph (i.e., the number of edges on the shortest path). 

In graph theory, the conversion of the adjacency matrix into the distance matrix is known as the all pairs shortest path problem , 

---

We tested our new potential by applying a local optimization procedure to the potential of some proteins, starting with the native structure as given in the Brookhaven Protein Data Bank, and observing how far the coordinates moved through local optimization. For a good potential, one expects the optimizer to be close to the native structure. As in Ulrich et al. [34], we measure the distance between optimizer B and native structure A by the distance matrix error... 

The Wiener index was originally defined only for acyclic graphs and was initially called the path number [6]. "The path number, W, is defined as the sum of the distances between any two carbon atoms in the molecule in terms of carbon-carbon bonds". Hosoya extended the Wiener index and defined it as the half-sum of the off diagonal elements of a distance matrix D in the hydrogen-depleted molecular graph of Eq, (15), where dij is an element of the distance matrix D and gives the shortest path between atoms i and j. 

Because of the symmetry of the distance matrix, the Wiener index can be expressed as Eq. (16). 

With Eq. (16) the Wiener index of compound 2 can be calculated from the distance matrix as shown in Eq, (17)... 

In the basic metric matrix implementation of the distance constraint technique [16] one starts by generating a distance bounds matrix. This is an A X y square matrix (N the number of atoms) in which the upper bounds occupy the upper diagonal and the lower bounds are placed in the lower diagonal. The matrix is Ailed by information based on the bond structure, experimental data, or a hypothesis. After smoothing the distance bounds matrix, a new distance matrix is generated by random selection of distances between the bounds. The distance matrix is converted back into a 3D confonnation after the distance matrix has been converted into a metric matrix and diagonalized. A new distance matrix... 

The distance matrix A, which holds the relative distances (by whatever similarity measure) between the individual confonnations, is rarely informative by itself. For example, when sampling along a molecular dynamics trajectory, the A matrix can have a block diagonal form, indicating that the trajectory has moved from one conformational basin to another. Nonetheless, even in this case, the matrix in itself does not give reliable information about the size and shape of the respective basins. In general, the distance matrix requires further processing. 

It should be stressed that PCA and PCoorA are dual methods that give the same analytical results. Using one or the other is simply a matter of convenience, whether one prefers to work with the covariance matrix C or with the distance matrix A. 

In a simple (nonweighted) connected graph, the graph distance dy between a pair of vertices V and Vj is equal to the length of the shortest path cormecting the two vertices, i.e. the number of edges on the shortest path. The distance between two adjacent vertices is 1. The distance matrix D(G) of a simple graph G with N vertices is the square NxN symmetric matrix in which [D],j=cl,j [9, 10]. 

The similarities between all pairs of objects are measured using one of the measures described earlier. This yields the similarity matrix or, if the distance is used as measure of (dis)similarity, the distance matrix. It is a symmetrical nx matrix containing the similarities between each pair of objects. Let us suppose, for example, that the meteorites A, B, C, D, and E in Table 30.3 have to be classified and that the distance measure selected is Euclidean distance. Using eq. (30.4), one obtains the similarity matrix in Table 30.4. Because the matrix is symmetrical, only half of this matrix needs to be used. 

W Wiener index — half-sum of the off-diagonal elements of the distance matrix of a graph... 

IC Information content of the distance matrix partitioned by frequency of occurrences of... 

All these distance measures allow a judgment of the similarity between the objects, and consequently the complete information between all n objects is contained in one-half of the n x n distance matrix. Thus, in case of a large number of objects, clustering algorithms that take the distance matrix into account are computationally not attractive, and one has to resort to other algorithms (see Section 6.3). 

The hierarchical clustering procedure operates on the distance matrix. Clustering of patterns is searched for by combining patterns with high similarity into gravity centres, in between the similar patterns. Here, a similarity scale runs from 1 to 0 according... 

The minimal spanning tree also operates on the distance matrix. Here, near by patterns are connected with lines in such a way that the sum of the connecting lines is minimal and no closed loops are constructed. Here too the information on distances is retained, but the mutual orientation of patterns is omitted. Both methods, hierarchical clustering and minimal spanning tree, aim for making clusters in the multi-dimensional space visible on a plane. 

The distance matrix D(G) of a graph G is another important graph-invariant. Its entries dy, called distances, are equal to the number of edges connecting the vertices i and j on the shortest path between them. Thus, all dy are integers, including du = 1 for nearest neighbours, and, by definition, d = 0. The distance matrix can be derived readily from the adjacency matrix ... 

For multiple edges (unsaturated or aromatic systems) fractional distances are introduced in the distance matrix so that fractional distance sums result on summation if the bond order between vertices i, j is b, then 1/b is the entry in the row/... 

We classified Z in the group of indices associated with the distance matrix (and not to the adjacency matrix, as Trinajstic did 21-22 ) due to the procedure for counting p(G, k). 

The classical definition for the graph centre is not helpful for cyclic graphs where often a large number of vertices (most of them topologically non-equivalent) appear as central. Recently, Bonchev, Balaban and Mekenyan 67) proposed a generalized concept for the graph centre, and several centric indices were derived on this basis. The new definition consists of four hierarchically ordered criteria based on the distance matrix 1) the smallest maximum distance in the row or column of the vertex ... 

Two types of information indices resulted from the statistical analysis of the distance matrix D(G) made by Bonchev and Trinajstic 34). Proceeding from Eq. (26), one can come to two distance partitions. In the first one, Pd, the total number of distances is partitioned into classes of distances, according to their equality or non-equality ... 

A is used to generate the distance matrix D [8-10]. D is a square n x n symmetric matrix in which the entry (D),y indicates the distance between vertices i and j, where the distance is the minimum number of edges between i and j. The maximum distance in D is denoted as dmax. D of G-I is... 

Mihalic, Z., S. Nikolic, and N. Trinajstic, Comparative Study of Molecular Descriptors Derived from the Distance Matrix. J. Chem. Inf. Comput. Sci., 1992 32, 28-37. 

Bersohn, M. A., A Fast Algorithm for Calculation of the Distance Matrix of a Molecule. 

N represents the number of sensors in the array. For p = 2, the distance in (10.10) is Euclidian. The protocol is relatively simple. The distance matrix is created from the datapoints and scanned for the smallest values that are then arranged and displayed in the form of a dendrogram (Fig. 10.9 Suslick, 2004) in which the dissimilarity is plotted on the horizontal axis. In a dendrogram, each horizontal line segment represents the distance—that is, the similarity—between samples. Thus, if we want... 

Prior to analysis, the Raman shift axes of the spectra were calibrated using the Raman spectrum of 4-acetamidophenol. Pretreatment of the raw spectra, such as vector normalization and calculation of derivatives were done using Matlab (The Mathworks, Inc.) or OPUS (Bruker) software. OPUS NT software (Bruker, Ettlingen, Germany) was used to perform the HCA. The first derivatives of the spectra were used over the range from 380 cm-1 to 1700 cm-1. To calculate the distance matrix, Euclidean distances were used and for clustering, Ward s algorithm was applied [59]. 

Fig. 4.3. Dendrogram resulting from cluster analysis containing 91 spectra from 15 tree species (see also Table 4.2). Cluster analysis was done on first derivatives over the spectral range 380 cm-1 to 1700 cm-1). The distance matrix was calculated using Euclidean distance and Ward s algorithm was applied for clustering. Spectra were measured after decomposition of carotenoid molecules with 633 nm irradiation. For example, spectra of each species are shown in Fig. 4.1. Reprinted with permission from [52]...

---