In bioinformatics, neighbor joining is a bottom-up (agglomerative) clustering method for the creation of phylogenetic trees, created by Naruya Saitou and Masatoshi Nei in 1987. [1] Usually based on DNA or protein sequence data, the algorithm requires knowledge of the distance between each pair of taxa (e.g., species or sequences) to create the phylogenetic tree. [2]
Neighbor joining takes a distance matrix, which specifies the distance between each pair of taxa, as input. The algorithm starts with a completely unresolved tree, whose topology corresponds to that of a star network, and iterates over the following steps, until the tree is completely resolved, and all branch lengths are known:
Based on a distance matrix relating the taxa, calculate the x matrix as follows:
| (1) |
where is the distance between taxa and .
For each of the taxa in the pair being joined, use the following formula to calculate the distance to the new node:
| (2) |
and:
Taxa and are the paired taxa and is the newly created node. The branches joining and and and , and their lengths, and are part of the tree which is gradually being created; they neither affect nor are affected by later neighbor-joining steps.
For each taxon not considered in the previous step, we calculate the distance to the new node as follows:
| (3) |
where is the new node, is the node which we want to calculate the distance to and and are the members of the pair just joined.
Neighbor joining on a set of taxa requires iterations. At each step one has to build and search a matrix. Initially the matrix is size , then the next step it is , etc. Implementing this in a straightforward way leads to an algorithm with a time complexity of ; [3] implementations exist which use heuristics to do much better than this on average. [4]
Let us assume that we have five taxa and the following distance matrix :
a | b | c | d | e | |
---|---|---|---|---|---|
a | 0 | 5 | 9 | 9 | 8 |
b | 5 | 0 | 10 | 10 | 9 |
c | 9 | 10 | 0 | 8 | 7 |
d | 9 | 10 | 8 | 0 | 3 |
e | 8 | 9 | 7 | 3 | 0 |
We calculate the values by equation ( 1 ). For example:
We obtain the following values for the matrix (the diagonal elements of the matrix are not used and are omitted here):
a | b | c | d | e | |
---|---|---|---|---|---|
a | −50 | −38 | −34 | −34 | |
b | −50 | −38 | −34 | −34 | |
c | −38 | −38 | −40 | −40 | |
d | −34 | −34 | −40 | −48 | |
e | −34 | −34 | −40 | −48 | |
In the example above, . This is the smallest value of , so we join elements and .
Let denote the new node. By equation ( 2 ), above, the branches joining and to then have lengths:
We then proceed to update the initial distance matrix into a new distance matrix (see below), reduced in size by one row and one column because of the joining of with into their neighbor . Using equation ( 3 ) above, we compute the distance from to each of the other nodes besides and . In this case, we obtain:
The resulting distance matrix is:
u | c | d | e | |
---|---|---|---|---|
u | 0 | 7 | 7 | 6 |
c | 7 | 0 | 8 | 7 |
d | 7 | 8 | 0 | 3 |
e | 6 | 7 | 3 | 0 |
Bold values in correspond to the newly calculated distances, whereas italicized values are not affected by the matrix update as they correspond to distances between elements not involved in the first joining of taxa.
The corresponding matrix is:
u | c | d | e | |
---|---|---|---|---|
u | −28 | −24 | −24 | |
c | −28 | −24 | −24 | |
d | −24 | −24 | −28 | |
e | −24 | −24 | −28 | |
We may choose either to join and , or to join and ; both pairs have the minimal value of , and either choice leads to the same result. For concreteness, let us join and and call the new node .
The lengths of the branches joining and to can be calculated:
The joining of the elements and the branch length calculation help drawing the neighbor joining tree as shown in the figure.
The updated distance matrix for the remaining 3 nodes, , , and , is now computed:
v | d | e | |
---|---|---|---|
v | 0 | 4 | 3 |
d | 4 | 0 | 3 |
e | 3 | 3 | 0 |
The tree topology is fully resolved at this point. However, for clarity, we can calculate the matrix. For example:
v | d | e | |
---|---|---|---|
v | −10 | −10 | |
d | −10 | −10 | |
e | −10 | −10 | |
For concreteness, let us join and and call the last node . The lengths of the three remaining branches can be calculated:
The neighbor joining tree is now complete, as shown in the figure.
This example represents an idealized case: note that if we move from any taxon to any other along the branches of the tree, and sum the lengths of the branches traversed, the result is equal to the distance between those taxa in the input distance matrix. For example, going from to we have . A distance matrix whose distances agree in this way with some tree is said to be 'additive', a property which is rare in practice. Nonetheless it is important to note that, given an additive distance matrix as input, neighbor joining is guaranteed to find the tree whose distances between taxa agree with it.
Neighbor joining may be viewed as a greedy heuristic for the balanced minimum evolution [5] (BME) criterion. For each topology, BME defines the tree length (sum of branch lengths) to be a particular weighted sum of the distances in the distance matrix, with the weights depending on the topology. The BME optimal topology is the one which minimizes this tree length. NJ at each step greedily joins that pair of taxa which will give the greatest decrease in the estimated tree length. This procedure does not guarantee to find the optimum for the BME criterion, although it often does and is usually quite close. [5]
The main virtue of NJ is that it is fast [6] : 466 as compared to least squares, maximum parsimony and maximum likelihood methods. [6] This makes it practical for analyzing large data sets (hundreds or thousands of taxa) and for bootstrapping, for which purposes other means of analysis (e.g. maximum parsimony, maximum likelihood) may be computationally prohibitive.
Neighbor joining has the property that if the input distance matrix is correct, then the output tree will be correct. Furthermore, the correctness of the output tree topology is guaranteed as long as the distance matrix is 'nearly additive', specifically if each entry in the distance matrix differs from the true distance by less than half of the shortest branch length in the tree. [7] In practice the distance matrix rarely satisfies this condition, but neighbor joining often constructs the correct tree topology anyway. [8] The correctness of neighbor joining for nearly additive distance matrices implies that it is statistically consistent under many models of evolution; given data of sufficient length, neighbor joining will reconstruct the true tree with high probability. Compared with UPGMA and WPGMA, neighbor joining has the advantage that it does not assume all lineages evolve at the same rate (molecular clock hypothesis).
Nevertheless, neighbor joining has been largely superseded by phylogenetic methods that do not rely on distance measures and offer superior accuracy under most conditions.[ citation needed ] Neighbor joining has the undesirable feature that it often assigns negative lengths to some of the branches.
There are many programs available implementing neighbor joining. Among implementations of canonical NJ (i.e. using the classical NJ optimisation criteria, therefore giving the same results), RapidNJ (started 2003, major update in 2011, still updated in 2023) [9] and NINJA (started 2009, last update 2013) [10] are considered state-of-the-art. They have typical run times proportional to approximately the square of the number of taxa.
Variants that deviate from canonical include:
In mathematical physics and mathematics, the Pauli matrices are a set of three 2 × 2 complex matrices which are Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries.
The moment of inertia, otherwise known as the mass moment of inertia, angular mass, second moment of mass, or most accurately, rotational inertia, of a rigid body is a quantity that determines the torque needed for a desired angular acceleration about a rotational axis, akin to how mass determines the force needed for a desired acceleration. It depends on the body's mass distribution and the axis chosen, with larger moments requiring more torque to change the body's rate of rotation by a given amount.
In numerical analysis, polynomial interpolation is the interpolation of a given bivariate data set by the polynomial of lowest possible degree that passes through the points of the dataset.
In mathematics, the Hodge star operator or Hodge star is a linear map defined on the exterior algebra of a finite-dimensional oriented vector space endowed with a nondegenerate symmetric bilinear form. Applying the operator to an element of the algebra produces the Hodge dual of the element. This map was introduced by W. V. D. Hodge.
UPGMA is a simple agglomerative (bottom-up) hierarchical clustering method. It also has a weighted variant, WPGMA, and they are generally attributed to Sokal and Michener.
In mathematics, computer science and especially graph theory, a distance matrix is a square matrix containing the distances, taken pairwise, between the elements of a set. Depending upon the application involved, the distance being used to define this matrix may or may not be a metric. If there are N elements, this matrix will have size N×N. In graph-theoretic applications, the elements are more often referred to as points, nodes or vertices.
In mechanics, virtual work arises in the application of the principle of least action to the study of forces and movement of a mechanical system. The work of a force acting on a particle as it moves along a displacement is different for different displacements. Among all the possible displacements that a particle may follow, called virtual displacements, one will minimize the action. This displacement is therefore the displacement followed by the particle according to the principle of least action.
The work of a force on a particle along a virtual displacement is known as the virtual work.
In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.
In solid-state physics, the tight-binding model is an approach to the calculation of electronic band structure using an approximate set of wave functions based upon superposition of wave functions for isolated atoms located at each atomic site. The method is closely related to the LCAO method used in chemistry. Tight-binding models are applied to a wide variety of solids. The model gives good qualitative results in many cases and can be combined with other models that give better results where the tight-binding model fails. Though the tight-binding model is a one-electron model, the model also provides a basis for more advanced calculations like the calculation of surface states and application to various kinds of many-body problem and quasiparticle calculations.
Mason's gain formula (MGF) is a method for finding the transfer function of a linear signal-flow graph (SFG). The formula was derived by Samuel Jefferson Mason, whom it is also named after. MGF is an alternate method to finding the transfer function algebraically by labeling each signal, writing down the equation for how that signal depends on other signals, and then solving the multiple equations for the output signal in terms of the input signal. MGF provides a step by step method to obtain the transfer function from a SFG. Often, MGF can be determined by inspection of the SFG. The method can easily handle SFGs with many variables and loops including loops with inner loops. MGF comes up often in the context of control systems, microwave circuits and digital filters because these are often represented by SFGs.
The Gaussian network model (GNM) is a representation of a biological macromolecule as an elastic mass-and-spring network to study, understand, and characterize the mechanical aspects of its long-time large-scale dynamics. The model has a wide range of applications from small proteins such as enzymes composed of a single domain, to large macromolecular assemblies such as a ribosome or a viral capsid. Protein domain dynamics plays key roles in a multitude of molecular recognition and cell signalling processes. Protein domains, connected by intrinsically disordered flexible linker domains, induce long-range allostery via protein domain dynamics. The resultant dynamic modes cannot be generally predicted from static structures of either the entire protein or individual domains.
In statistics, single-linkage clustering is one of several methods of hierarchical clustering. It is based on grouping clusters in bottom-up fashion, at each step combining two clusters that contain the closest pair of elements not yet belonging to the same cluster as each other.
Shape context is a feature descriptor used in object recognition. Serge Belongie and Jitendra Malik proposed the term in their paper "Matching with Shape Contexts" in 2000.
In fracture mechanics, the energy release rate, , is the rate at which energy is transformed as a material undergoes fracture. Mathematically, the energy release rate is expressed as the decrease in total potential energy per increase in fracture surface area, and is thus expressed in terms of energy per unit area. Various energy balances can be constructed relating the energy released during fracture to the energy of the resulting new surface, as well as other dissipative processes such as plasticity and heat generation. The energy release rate is central to the field of fracture mechanics when solving problems and estimating material properties related to fracture and fatigue.
Defect types include atom vacancies, adatoms, steps, and kinks that occur most frequently at surfaces due to the finite material size causing crystal discontinuity. What all types of defects have in common, whether surface or bulk defects, is that they produce dangling bonds that have specific electron energy levels different from those of the bulk. This difference occurs because these states cannot be described with periodic Bloch waves due to the change in electron potential energy caused by the missing ion cores just outside the surface. Hence, these are localized states that require separate solutions to the Schrödinger equation so that electron energies can be properly described. The break in periodicity results in a decrease in conductivity due to defect scattering.
In mathematics, Weingarten functions are rational functions indexed by partitions of integers that can be used to calculate integrals of products of matrix coefficients over classical groups. They were first studied by Weingarten (1978) who found their asymptotic behavior, and named by Collins (2003), who evaluated them explicitly for the unitary group.
Complete-linkage clustering is one of several methods of agglomerative hierarchical clustering. At the beginning of the process, each element is in a cluster of its own. The clusters are then sequentially combined into larger clusters until all elements end up being in the same cluster. The method is also known as farthest neighbour clustering. The result of the clustering can be visualized as a dendrogram, which shows the sequence of cluster fusion and the distance at which each fusion took place.
WPGMA is a simple agglomerative (bottom-up) hierarchical clustering method, generally attributed to Sokal and Michener.
In two-dimensional conformal field theory, Virasoro conformal blocks are special functions that serve as building blocks of correlation functions. On a given punctured Riemann surface, Virasoro conformal blocks form a particular basis of the space of solutions of the conformal Ward identities. Zero-point blocks on the torus are characters of representations of the Virasoro algebra; four-point blocks on the sphere reduce to hypergeometric functions in special cases, but are in general much more complicated. In two dimensions as in other dimensions, conformal blocks play an essential role in the conformal bootstrap approach to conformal field theory.
A central problem in algorithmic graph theory is the shortest path problem. One of the generalizations of the shortest path problem is known as the single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex to all other vertices in the graph. There are classical sequential algorithms which solve this problem, such as Dijkstra's algorithm. In this article, however, we present two parallel algorithms solving this problem.
{{cite journal}}
: CS1 maint: multiple names: authors list (link){{cite book}}
: |journal=
ignored (help)