This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Distance matrix" – news ·newspapers ·books ·scholar ·JSTOR(February 2017) (Learn how and when to remove this message)

Inmathematics,computer science and especiallygraph theory, adistance matrix is asquare matrix (two-dimensional array) containing thedistances, taken pairwise, between the elements of a set.^[1] Depending upon the application involved, thedistance being used to define this matrix may or may not be ametric. If there areN elements, this matrix will have sizeN×N. In graph-theoretic applications, the elements are more often referred to as points, nodes or vertices.

In general, a distance matrix is a weightedadjacency matrix of some graph. In anetwork, adirected graph with weights assigned to the arcs, the distance between two nodes of the network can be defined as the minimum of the sums of the weights on the shortest paths joining the two nodes (where the number of steps in the path is bounded).^[2] This distance function, while well defined, is not a metric. There need be no restrictions on the weights other than the need to be able to combine and compare them, so negative weights are used in some applications. Since paths are directed, symmetry can not be guaranteed, and if negative-weight cycles exist the distance matrix may not behollow (and in the absence of a bound on the step count, the matrix may be undefined).

An algebraic formulation of the above can be obtained by using themin-plus algebra. Matrix multiplication in this system is defined as follows: Given twon ×n matricesA = (a_ij) andB = (b_ij), their distance productC = (c_ij) =A ⭑B is defined as ann ×n matrix such that

${\displaystyle c_{ij}=\underset{k=1}{\overset{n}{min}}\{a_{ik}+b_{kj}\}.}$

Note that the off-diagonal elements that are not connected directly will need to be set to infinity or a suitable large value for the min-plus operations to work correctly. A zero in these locations will be incorrectly interpreted as an edge with no distance, cost, etc.

IfW is ann ×n matrix containing the edge weights of agraph, thenW^k (using this distance product) gives the distances between vertices using paths of length at mostk edges, and so is the distance matrix of the graph when the step count bound is set tok. If there are no loops of negative weight,Wⁿ will give the true distance matrix, with no bound, because removing repeated vertices from a path cannot lower its weight. On the other hand, ifi andj are on a negative-weight loop,W^k_ij will decrease without bound ask increases.

An arbitrary graphG onn vertices can be modeled as a weightedcomplete graph onn vertices by assigning a weight of one to each edge of the complete graph that corresponds to an edge ofG and infinity to all other edges.W for this complete graph is theadjacency matrix ofG. The distance matrix ofG can be computed fromW as above; by contrast, if normal matrix multiplication is used, and unlinked vertices are represented with 0,Wⁿ would instead encode the number of paths between any two vertices of length exactlyn.

The value of a distance matrix formalism in many applications is in how the distance matrix can manifestly encode themetric axioms and in how it lends itself to the use of linear algebra techniques. That is, ifM = (x_ij) with1 ≤i,j ≤N is a distance matrix for a metric distance, then

1. the entries on the main diagonal are all zero (that is, the matrix is ahollow matrix), i.e.x_ii = 0 for all1 ≤i ≤N,
2. all the off-diagonal entries are positive (x_ij > 0 ifi ≠j), (that is, anon-negative matrix),
3. the matrix is asymmetric matrix (x_ij =x_ji), and
4. for anyi andj,x_ij ≤x_ik +x_kj for allk (the triangle inequality). This can be stated in terms oftropical matrix multiplication

When a distance matrix satisfies the first three axioms (making it a semi-metric) it is sometimes referred to as a pre-distance matrix. A pre-distance matrix that can be embedded in a Euclidean space is called aEuclidean distance matrix. For mixed-type data that contain numerical as well as categorical descriptors,Gower's distance is a common alternative.

Another common example of a metric distance matrix arises incoding theory when in ablock code the elements are strings of fixed length over an alphabet and the distance between them is given by theHamming distance metric. The smallest non-zero entry in the distance matrix measures the error correcting and error detecting capability of the code.

An additive distance matrix is a special type of matrix used inbioinformatics to build aphylogenetic tree. Letx be the lowest common ancestor between two speciesi andj, we expectM_ij =M_ix +M_xj. This is where the additive metric comes from. A distance matrixM for a set of speciesS is said to be additive if and only if there exists a phylogenyT forS such that:

• Every edge(u,v) inT is associated with a positive weightd_uv
• For everyi,j ∈S,M_ij equals the sum of the weights along the path fromi toj inT

For this case,M is called an additive matrix andT is called an additive tree. Below we can see an example of an additive distance matrix and its corresponding tree:

The ultrametric distance matrix is defined as an additive matrix which models the constantmolecular clock. It is used to build a phylogenetic tree. A matrixM is said to be ultrametric if there exists a treeT such that:

• M_ij equals the sum of the edge weights along the path fromi toj inT
• A root of the tree can be identified with the distance to all the leaves being the same

Here is an example of an ultrametric distance matrix with its corresponding tree:

This sectionis missing information about alignment-free distance measures (Mash, K(r), FastANI, Skmer etc.); need less weight on how to do alignment (especially with "dumb" DP) and more weight on how to get distance from alignment. Please expand the section to include this information. Further details may exist on thetalk page.(December 2023)

The distance matrix is widely used in the bioinformatics field, and it is present in several methods, algorithms and programs. Distance matrices are used to representprotein structures in a coordinate-independent manner, as well as the pairwise distances between two sequences insequence space. They are used instructural andsequential alignment, and for the determination of protein structures fromNMR orX-ray crystallography.

Sometimes it is more convenient to express data as asimilarity matrix.

It is also used to define thedistance correlation.

An alignment of two sequences is formed by inserting spaces in arbitrary locations along the sequences so that they end up with the same length and there are no two spaces at the same position of the two augmented sequences.^[3] One of the primary methods for sequence alignment isdynamic programming. The method is used to fill the distance matrix and then obtain the alignment. In typical usage, for sequence alignment a matrix is used to assign scores to amino-acid matches or mismatches, and a gap penalty for matching an amino-acid in one sequence with a gap in the other.

TheNeedleman–Wunsch algorithm used to calculate global alignment uses dynamic programming to obtain the distance matrix.

TheSmith–Waterman algorithm is also dynamic programming based which consists also in obtaining the distance matrix and then obtain the local alignment.

Multiple sequence alignment is an extension of pairwise alignment to align several sequences at a time. Different MSA methods are based on the same idea of the distance matrix as global and local alignments.

• Center star method. This method defines a center sequenceS_c which minimizes the distance between the sequenceS_c and any other sequenceS_i. Then it generates a multiple alignmentM for the set of sequencesS so that for everyS_i the alignment distanced_M(S_c,S_i) is the optimal pairwise alignment. This method has the characteristic that the computed alignment forS whose sum-of-pair distance is at most twice the optimal multiple alignment.
• Progressive alignment method. This heuristic method to create MSA first aligns the two most related sequences, and then it progressively aligns the next two most related sequences until all sequences are aligned.

There are other methods that have their own program due to their popularity:

• ClustalW
• MUSCLE
• MAFFT
• MANGO
• And many more

Multiple alignment using fast Fourier transform (MAFFT) is a program with an algorithm based on progressive alignment, and it offers various multiple alignment strategies. First, MAFFT constructs a distance matrix based on the number of shared 6-tuples. Second, it builds the guide tree based on the previous matrix. Third, it clusters the sequences with the help of thefast Fourier transform and starts the alignment. Based on the new alignment, it reconstructs the guide tree and align again.

This section mayrequirecleanup to meet Wikipedia'squality standards. The specific problem is:Should be trimmed down and mostly packed up to the main article. That's howWP:SPINOFF works, right? Please helpimprove this section if you can.(December 2023) (Learn how and when to remove this message)

To performphylogenetic analysis, the first step is to reconstruct the phylogenetic tree: given a collection of species, the problem is to reconstruct or infer the ancestral relationships among the species, i.e., the phylogenetic tree among the species. Distance matrix methods perform this activity.

Distance matrix methods of phylogenetic analysis explicitly rely on a measure of "genetic distance" between the sequences being classified, and therefore require multiple sequences as an input. Distance methods attempt to construct an all-to-all matrix from the sequence query set describing the distance between each sequence pair. From this is constructed a phylogenetic tree that places closely related sequences under the sameinterior node and whose branch lengths closely reproduce the observed distances between sequences. Distance-matrix methods may produce either rooted or unrooted trees, depending on the algorithm used to calculate them.^[4] Givenn species, the input is ann ×n distance matrixM whereM_ij is the mutation distance between speciesi andj . The aim is to output a tree of degree3 which is consistent with the distance matrix.

They are frequently used as the basis for progressive and iterative types ofmultiple sequence alignment. The main disadvantage of distance-matrix methods is their inability to efficiently use information about local high-variation regions that appear across multiple subtrees.^[4] Despite potential problems, distance methods are extremely fast, and they often produce a reasonable estimate of phylogeny. They also have certain benefits over the methods that use characters directly. Notably, distance methods allow use of data that may not be easily converted to character data, such asDNA–DNA hybridization assays.

The following are distance based methods for phylogeny reconstruction:

• Additive tree reconstruction
• UPGMA
• Neighbor joining
• Fitch–Margoliash

Additive tree reconstruction is based on additive and ultrametric distance matrices. These matrices have a special characteristic:

Consider an additive matrixM. For any three speciesi, j, k, the corresponding tree is unique.^[3] Every ultrametric distance matrix is an additive matrix. We can observe this property for the tree below, which consists on the speciesi, j, k.

The additive tree reconstruction technique starts with this tree. And then adds one more species each time, based on the distance matrix combined with the property mentioned above. For example, consider an additive matrixM and 5 speciesa,b,c,d ande. First we form an additive tree for two speciesa andb. Then we chose a third one, let's sayc and attach it to a pointx on the edge betweena andb. The edge weights are computed with the property above. Next we add the fourth speciesd to any of the edges. If we apply the property then we identify thatd should be attached to only one specific edge. Finally, we adde following the same procedure as before.

The basic principle of UPGMA (Unweighted Pair Group Method with Arithmetic Mean) is that similar species should be closer in the phylogenetic tree. Hence, it builds the tree by clustering similar sequences iteratively. The method works by building the phylogenetic tree bottom up from its leaves. Initially, we haven leaves (orn singleton trees), each representing a species inS. Thosen leaves are referred asn clusters. Then, we performn-1 iterations. In each iteration, we identify two clustersC₁ andC₂ with the smallest average distance and merge them to form a bigger clusterC. If we supposeM is ultrametric, for any clusterC created by the UPGMA algorithm,C is a valid ultrametric tree.

Neighbor is a bottom-up clustering method. It takes a distance matrix specifying the distance between each pair of sequences. The algorithm starts with a completely unresolved tree, whose topology corresponds to that of astar network, and iterates over the following steps until the tree is completely resolved and all branch lengths are known:

1. Based on the current distance matrix calculate the matrix (defined below).
2. Find the pair of distinct taxa i and j (i.e. with) for which has its lowest value. These taxa are joined to a newly created node, which is connected to the central node.
3. Calculate the distance from each of thetaxa in the pair to this new node.
4. Calculate the distance from each of the taxa outside of this pair to the new node.
5. Start the algorithm again, replacing the pair of joined neighbors with the new node and using the distances calculated in the previous step.^[5]

The Fitch–Margoliash method uses a weightedleast squares method for clustering based on genetic distance. Closely related sequences are given more weight in the tree construction process to correct for the increased inaccuracy in measuring distances between distantly related sequences. The least-squares criterion applied to these distances is more accurate but less efficient than the neighbor-joining methods. An additional improvement that corrects for correlations between distances that arise from many closely related sequences in the data set can also be applied at increased computational cost.^[6]

A common function in data mining is applyingcluster analysis on a given set of data to group data based on how similar or more similar they are when compared to other groups. Distance matrices became heavily dependent and utilized incluster analysis since similarity can be measured with a distance metric. Thus, distance matrix became the representation of the similarity measure between all the different pairs of data in the set.

A distance matrix is necessary for traditionalhierarchical clustering algorithms which are often heuristic methods employed in biological sciences such as phylogeny reconstruction. When implementing any of the hierarchical clustering algorithms in data mining, the distance matrix will contain all pair-wise distances between every point and then will begin to create clusters between two different points or clusters based entirely on distances from the distance matrix.

If N be the number of points, the complexity of hierarchical clustering is:

• Time complexity is${\displaystyle O(N^3)}$ due to the repetitive calculations done after every cluster to update the distance matrix
• Space complexity is${\displaystyle O(N^2)}$

Distance metrics are a key part of several machine learning algorithms, which are used in bothsupervised andunsupervised learning. They are generally used to calculate the similarity between data points: this is where the distance matrix is an essential element. The use of an effective distance matrix improves the performance of the machine learning model, whether it is for classification tasks or for clustering.^[7]

A distance matrix is utilized in thek-NN algorithm which is one of the slowest but simplest and most used instance-based machine learning algorithms that can be used both in classification and regression tasks. It is one of the slowest machine learning algorithms since each test sample's predicted result requires a fully computed distance matrix between the test sample and each training sample in the training set. Once the distance matrix is computed, the algorithm selects the K number of training samples that are the closest to the test sample to predict the test sample's result based on the selected set's majority (classification) or average (regression) value.

• Prediction time complexity is${\displaystyle O(k\ast n\ast d)}$, to compute the distance between each test sample with every training sample to construct the distance matrix where:

1. k = number of nearest neighbors selected
2. n = size of the training set
3. d = number of dimensions being used for the data

This classification focused model predicts the label of the target based on the distance matrix between the target and each of the training samples to determine the K-number of samples that are the closest/nearest to the target.

A distance matrix can be used inneural networks for 2D to 3D regression in image predicting machine learning models.

• [1]* Gaussian mixture distance for performing accuratenearest neighbor search for information retrieval. Under an established Gaussian finite mixture model for the distribution of the data in the database, the Gaussian mixture distance is formulated based on minimizing theKullback–Leibler divergence between the distribution of the retrieval data and the data in database. In the comparison of performance of the Gaussian mixture distance with the well-knownEuclidean andMahalanobis distances based on a precision performance measurement, experimental results demonstrate that the Gaussian mixture distance function is superior in the others for different types of testing data.

Potential basic algorithms worth noting on the topic of information retrieval isFish School Search algorithm an information retrieval that partakes in the act of using distance matrices in order for gathering collective behavior of fish schools. By using a feeding operator to update their weights

Eq. A:

${\displaystyle x_i(t+1)=x_i(t)-ste{p}_{vol}rand(0,1)\frac{x_i(t)-B(t)}{distance(x_i(t),B(t))},}$

Eq. B:

${\displaystyle x_i(t+1)=x_i(t)+ste{p}_{vol}rand(0,1)\frac{x_i(t)-B(t)}{distance(x_i(t),B(t))},}$

Stepvol defines the size of the maximum volume displacement preformed with the distance matrix, specifically using aEuclidean distance matrix.

• [2] While theCosine similarity measure is perhaps the most frequently applied proximity measure in information retrieval by measuring the angles between documents in the search space on the base of the cosine. Euclidean distance is invariant to mean-correction. The sampling distribution of a mean is generated by repeated sampling from the same population and recording of the sample means obtained. This forms a distribution of different means, and this distribution has its own mean and variance. For the data which can be negative as well as positive, thenull distribution for cosine similarity is the distribution of thedot product of two independent random unit vectors. This distribution has a mean of zero and a variance of 1/n. WhileEuclidean distance will be invariant to this correction.

The implementation ofhierarchical clustering with distance-based metrics to organize and group similar documents together will require the need and utilization of a distance matrix. The distance matrix will represent the degree of association that a document has with another document that will be used to create clusters of closely associated documents that will be utilized in retrieval methods of relevant documents for a user's query.

Isomap incorporates distance matrices to utilizegeodesic distances to able to compute lower-dimensional embeddings. This helps to address a collection of documents that reside within a massive number of dimensions and empowers to perform document clustering.

An algorithm used for both unsupervised and supervised visualization that uses distance matrices to find similar data based on the similarities shown on a display/screen.

The distance matrix needed for Unsupervised NeRV can be computed through fixed input pairwise distances.

The distance matrix needed for Supervised NeRV requires formulating a supervised distance metric to be able to compute the distance of the input in a supervised manner.

The distance matrix is a mathematical object widely used in both graphical-theoretical (topological) and geometric (topographic) versions of chemistry.^[8] The distance matrix is used in chemistry in both explicit and implicit forms.

Distance matrices were used as the main approach to depict and reveal the shortest path sequence needed to determine the rearrangement between the two permutational isomers.

Explicit use of Distance matrices is required in order to construct the distance polynomials and distance spectra of molecular structures.

Implicit use of Distance matrices was applied through the use of the distance based metricWeiner number/Weiner Index which was formulated to represent the distances in all chemical structures. The Weiner number is equal to half-sum of the elements of the distance matrix.

Distance matrix in chemistry that are used for the 2-D realization of molecular graphs, which are used to illustrate the main foundational features of a molecule in a myriad of applications.

1. Creating a label tree that represents thecarbon skeleton of a molecule based on its distance matrix. The distance matrix is imperative in this application because similar molecules can have a myriad of label tree variants of theircarbon skeleton. The labeled tree structure ofhexane (C₆H₁₄) carbon skeleton that is created based on the distance matrix in the example, has different carbon skeleton variants that affect both the distance matrix and the labeled tree
2. Creating a labeled graph with edge weights, used inchemical graph theory, that represent molecules with hetero-atoms.
3. Le Verrier-Fadeev-Frame (LVFF) method is a computer oriented used to speed up the process of detecting the graph center in polycyclic graphs. However, LVFF requires the input to be a diagonalized distance matrix which is easily resolved by implementing the Householder tridiagonal-QL algorithm that takes in a distance matrix and returns the diagonalized distance needed for the LVFF method.

While the graph-theoretical distance matrix 2-D captures the constitutional features of the molecule, its three-dimensional (3D) character is encoded in the geometric-distance matrix. The geometric-distance matrix is a different type of distance matrix that is based on the graph-theoretical distance matrix of a molecule to represent and graph the 3-D molecule structure.^[8] The geometric-distance matrix of a molecular structureG is a real symmetricn xn matrix defined in the same way as a 2-D matrix. However, the matrix elementsD_ij will hold a collection of shortest Cartesian distances betweeni andj inG. Also known as topographic matrix, the geometric-distance matrix can be constructed from the known geometry of the molecule. As an example, the geometric-distance matrix of the carbon skeleton of2,4-dimethylhexane is shown below:

Dynamic Time Warping distance matrices are utilized with the clustering and classification algorithms of a collection/group of time series objects.

For example, suppose these data are to be analyzed, wherepixelEuclidean distance is thedistance metric.

The distance matrix would be:

These data can then be viewed in graphic form as aheat map. In this image, black denotes a distance of 0 and white is maximal distance.

• Computer vision
• Data clustering
• Distance set
• Hollow matrix
• Min-plus matrix multiplication

• Metric geometry
• Bioinformatics
• Matrices (mathematics)
• Graph distance

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from February 2017
• All articles needing additional references
• Articles to be expanded from December 2023
• Articles needing cleanup from December 2023
• All pages needing cleanup
• Cleanup tagged articles with a reason field from December 2023
• Wikipedia pages needing cleanup from December 2023