In mathematics, computer science and especially graph theory, a distance matrix is a square matrix (two-dimensional array) containing the distances, taken pairwise, between the elements of a set.Weyenberg, G., & Yoshida, R. (2015). Reconstructing the phylogeny: Computational methods. In Algebraic and Discrete Mathematical methods for modern Biology (pp. 293–319). Academic Press. Depending upon the application involved, the "distance" being used to define this matrix may or may not be a metric. If there are elements, this matrix will have size . In graph-theoretic applications, the elements are usually referred to as points, nodes or vertices.
Non-metric distance matrix In general, a distance matrix is a weighted adjacency matrix of some graph. In a network, a directed 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).Frank Harary, Robert Z. Norman and Dorwin Cartwright (1965) Structural Models: An Introduction to the Theory of Directed Graphs, pages 134–8, John Wiley & Sons 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 be hollow (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 the min-plus algebra. Matrix multiplication in this system is defined as follows: Given two matrices and , their distance product is defined as an matrix such that
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.
If is an matrix containing the edge weights of a graph, then (using this distance product) gives the distances between vertices using paths of length at most edges, and so is the distance matrix of the graph when the step count bound is set to k. If there are no loops of negative weight, will give the true distance matrix, with no bound, because removing repeated vertices from a path cannot lower its weight. On the other hand, if i and j are on a negative-weight loop, will decrease without bound as k increases.
An arbitrary graph on vertices can be modeled as a weighted complete graph on vertices by assigning a weight of one to each edge of the complete graph that corresponds to an edge of and infinity to all other edges. for this complete graph is the adjacency matrix of . The distance matrix of can be computed from as above; by contrast, if normal matrix multiplication is used, and unlinked vertices are represented with 0, would instead encode the number of paths between any two vertices of length exactly .
Metric distance matrix The value of a distance matrix formalism in many applications is in how the distance matrix can manifestly encode the metric axioms and in how it lends itself to the use of linear algebra techniques. That is, if with is a distance matrix for a metric distance, then
the entries on the main diagonal are all zero (that is, the matrix is a hollow matrix), i.e. for all , all the off-diagonal entries are positive ( if ), (that is, a non-negative matrix), the matrix is a symmetric matrix (), and for any and , for all (the triangle inequality). This can be stated in terms of tropical 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 a Euclidean 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 in coding theory when in a block code the elements are strings of fixed length over an alphabet and the distance between them is given by the Hamming distance metric. The smallest non-zero entry in the distance matrix measures the error correcting and error detecting capability of the code.
Additive distance matrix An additive distance matrix is a special type of matrix used in bioinformatics to build a phylogenetic tree. Let be the lowest common ancestor between two species and , we expect . This is where the additive metric comes from. A distance matrix for a set of species is said to be additive if and only if there exists a phylogeny for such that:
Every edge in is associated with a positive weight For every , equals the sum of the weights along the path from to in
For this case, is called an additive matrix and is called an additive tree. Below we can see an example of an additive distance matrix and its corresponding tree:
Ultrametric distance matrix The ultrametric distance matrix is defined as an additive matrix which models the constant molecular clock. It is used to build a phylogenetic tree. A matrix is said to be ultrametric if there exists a tree such that:
equals the sum of the edge weights along the path from to in 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:
Bioinformatics
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 represent protein structures in a coordinate-independent manner, as well as the pairwise distances between two sequences in sequence space. They are used in structural and sequential alignment, and for the determination of protein structures from NMR or X-ray crystallography.
Sometimes it is more convenient to express data as a similarity matrix.
It is also used to define the distance correlation.
Sequence alignment 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. One of the primary methods for sequence alignment is dynamic 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.
Global alignment The Needleman–Wunsch algorithm used to calculate global alignment uses dynamic programming to obtain the distance matrix.
Local alignment The Smith–Waterman algorithm is also dynamic programming based which consists also in obtaining the distance matrix and then obtain the local alignment.
Multiple sequence 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 sequence which minimizes the distance between the sequence and any other sequence . Then it generates a multiple alignment for the set of sequences so that for every the alignment distance is the optimal pairwise alignment. This method has the characteristic that the computed alignment for 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
MAFFT 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 the fast Fourier transform and starts the alignment. Based on the new alignment, it reconstructs the guide tree and align again.
Phylogenetic analysis
To perform phylogenetic 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 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 same interior 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. Given species, the input is an distance matrix where is the mutation distance between species and . The aim is to output a tree of degree which is consistent with the distance matrix.
They are frequently used as the basis for progressive and iterative types of multiple 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. 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 as DNA–DNA hybridization assays.
The following are distance based methods for phylogeny reconstruction:
Additive tree reconstruction UPGMA Neighbor joining Fitch–Margoliash
Additive tree reconstruction Additive tree reconstruction is based on additive and ultrametric distance matrices. These matrices have a special characteristic:
Consider an additive matrix . For any three species the corresponding tree is unique. Every ultrametric distance matrix is an additive matrix. We can observe this property for the tree below, which consists on the species .
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 matrix and 5 species and . First we form an additive tree for two species and . Then we chose a third one, let's say and attach it to a point on the edge between and . The edge weights are computed with the property above. Next we add the fourth species to any of the edges. If we apply the property then we identify that should be attached to only one specific edge. Finally, we add following the same procedure as before.
UPGMA