Minimum Evolution (ME) is a phylogenetic tree building method. It uses a pairwise distance matrix, calculated from a multiple sequence alignment, to generate a phylogenetic tree. ME evaluates different tree arrangements by estimating branch lengths that best fit the distance data, then selects the branching pattern with the smallest total branch length.
The modern minimum evolution framework was first used by Kenneth Kidd and Sgaramella-Zonta (1971), and later independently developed further by Andrey Rzhetsky and Masatoshi Nei (1992). This method should not be confused with the earlier minimum evolution, maximum parsimony-based method proposed by Edwards and Cavalli-Sforza (1964); while the methods both share goal of searching for a tree with the shortest total sum of branch lengths, the implementations differ, as ME has a statistical foundation that does not rely solely on Occam's razor reasoning, compared to its earlier predecessor.
Minimum evolution has helped establish several key ideas in phylogenetics: It reinforced the principle that the best phylogenetic tree may be the one that minimizes the total amount of inferred evolutionary change. It played a major role in shaping distance based phylogenetic algorithms, influencing the development of widely used algorithms such as neighbor joining. By framing tree reconstruction as an optimization theory problem solved using heuristic approaches, it also helped lay the groundwork for many modern fast heuristic tree search methods.
Relationships with and comparison with other methods
Summary Minimum evolution is one of several algorithms used to reconstruct phylogenetic trees, each differing in the type of input data, optimal criterion, and computational time. Distance based methods like ME, Neighbor Joining and UPGMA reduce sequence data to a pairwise distance matrix, while character-based methods like Maximum parsimony operate directly with the aligned sequences. Model-based methods like Maximum Likelihood also incorporate explicit substitution model. Understanding how Minimum evolution relate to these alternatives showcases its strengths and the trade-offs involved in method selection. + Comparison Table for Phylogenetic Tree-Building Methods Principle Usage Case Time Complexity Minimum Evolution (ME) Searches for the shortest total sum of branch lengths Large datasets where character-based methods would be too demanding NP-hard without utilizing heuristics Maximum Parsimony Searches for the minimal number of evolutionary steps (i.e. mutations) Similar sequence comparisons NP-hard for large datasets Neighbor Joining Iteratively joins the shortest branch lengths to construct a single tree Large datasets / Datasets with few informative sites O(N3), can be improved using heuristics Maximum LikelihoodLooks for the most probable function possible given data parametersLarge datasets where low bias is importantO(N), this improves with larger datasetsUnweighted Pair Group Method with Arithmetic Mean(UPGMA)Creates a cluster of clusters and finds the arithmetic mean of the clustersInitial examination of dataO(N2)
Relationship comparison There is no single phylogenetic method that dominates across all scenarios. Each of the different algorithms have their own strengths and weaknesses when it comes to what they are able to accomplish. picking the right one ultimately depends on what the priorities of a given analysis are. UPGMA is the simplest and fastest option however, it is only appropriate when a molecular clock is present. Neighbor Joining approximates the Minimum Evolution optimum using an efficient algorithm O(N3) which makes it very useful when working with large datasets. Maximum Parsimony is good at looking at each individual position in the DNA or protein sequence and tracking exactly that changed however, it scales poorly and would not be the best pick if you were working with large amounts of data as it would be very slow. Maximum Likelihood is easily the most accurate method when using a well-specified model but it has the heaviest computation so it would not be very practical to use if you were working with larger datasets as well. Overall, Minimum Evolution tends to be in the middle ground it is more rigorous than UPGMA and Neighbor Joining while also being more scalable than some of the more accurate algorithms like Maximum Parsimony and Maximum Likelihood This would make it useful for a large variety of cases which explains why its widely used in modern phylogenetics.
Maximum parsimony
It is worth noting here a subtle difference between the maximum-parsimony criterion and the ME criterion: while maximum-parsimony is based on an abductive heuristic, i.e., the plausibility of the simplest evolutionary hypothesis of taxa with respect to the more complex ones, the ME criterion is based on Kidd and Sgaramella-Zonta's conjectures that were proven true 22 years later by Rzhetsky and Nei. These mathematical results set the ME criterion free from the Occam's razor principle and confer it a solid theoretical and quantitative basis.
Similarly to ME, maximum parsimony becomes an NP-hard problem when trying to find the optimal tree (that is, the one with the least total character-state changes). This is why heuristics are often utilized in order to select a tree, though this does not guarantee the tree will be an optimal selection for the input dataset. This method is often used when very similar sequences are analyzed, as part of the process is locating informative sites in the sequences where a notable number of substitutions can be found.
Maximum-parsimony criterion, which uses Hamming distance branch lengths, was shown to be statistically inconsistent in 1978. This led to an interest in statistically consistent alternatives such as ME.
Neighbor joining
Neighbor joining may be viewed as a greedy heuristic for the balanced minimum evolution (BME) criterion. Saito and Nei's 1987 NJ algorithm far predates the BME criterion of 2000. For two decades, researchers used NJ without a firm theoretical basis for why it works.
While neighbor joining shares the same underlying principle of prioritizing minimal evolutionary steps, it differs in that it is a distance method as opposed to maximum parsimony, which is a character-based method. Distance methods like neighbor joining are often simpler to implement and more efficient, which has led to its popularity for analyzing especially large datasets where computational speed is critical. Neighbor joining is a relatively fast phylogenetic tree-building method, though its worst-case time complexity can still be O(N3) without utilizing heuristic implementations to improve on this. It also considers varying rates of evolution across branches, which many other methods do not account for.
Neighbor joining also is a rather consistent method in that an input distance matrix with little to no errors will often provide an output tree with minimal inaccuracy. However, using simple distance values rather than full sequence information like in maximum parsimony does lend itself to a loss of information due to the simplification of the problem.
Maximum likelihood
Maximum Likelihood differs from Minimum Evolution in the sense that it calculates likelihood , evaluating many different phylogenetic trees and selecting the one that maximizes the probability of observing the data under a substitution model .Felsenstein J. Evolutionary trees from DNA sequences: a maximum likelihood approach. J Mol Evol. 1981;17(6):368-376. doi: 10.1007/BF01734359. PMID 7288891
This is done by utilizing the pulley principle, which says that under certain models, the placement of the root in the tree does not affect the likelihood score. While Minimum Evolution focuses on minimizing total branch length, Maximum Likelihood is based on statistical probability and incorporates models of evolutionary change.
Maximum Likelihood methods are generally more flexible and less-biased when sufficient data are available, but are more computationally intensive. Due to the complexity of the model, they may be less reliable with smaller datasets. Compared to simpler methods like UPGMA, Maximum Likelihood is much more powerful but also more complicated and computationally demanding.
UPGMA
UPGMA is a clustering method. It builds a collection of clusters that are then further clustered until the maximum potential cluster is obtained. This is then worked backwards to determine the relation of the groups. It specifically uses an arithmetic mean enabling a more stable clustering. Overall while it is less powerful compared to any of the other listed comparisons it is far simpler and less complex to create. Minimal Evolution is overall more powerful but also more complicated to set up, and is also NP hard.
Statistical consistency The ME criterion is known to be statistically consistent, meaning the method is mathematically guaranteed to converge on the true evolutionary tree as the amount of genetic data increases. That consistency was established by Andrey Rzhetsky and Masatoshi Nei, who proved that when the branch lengths are estimated via the Ordinary Least-Squares (OLS), the true tree topology will yield the smallest expected sum of branch lengths, provided the evolutionary distances used are statistically unbiased. However, Rzhetsky & Nei also showed that the phylogeny having the minimum length under the OLS branch length estimation model, in some circumstance, may be characterized by negative branch lengths, which unfortunately are empty of biological meaning.
The standard OLS model assumes all distance measurements are equally reliable. However, biological datasets typically involve unequal variances and covariances, meaning some distance estimates are noisier than others. While Weighted Least-Squares (WLS) and Generalized Least-Squares (GLS) were explored to account for these statistical differences, Francois Denis and Olivier Gascuel proved that the Minimum Evolution principle is not consistent in WLS and GLS. They identified that for the ME principle to remain consistent, a model must satisfy certain mathematical requirement called the EDGE_LENGTHS property. In OLS framework, this property allows the length of an internal branch to be calculated using only the distance between taxa directly adjacent to those nodes. This property does not exist in standard WLS and GLS models. Thus, ME principle is not consistent in the WLS and GLS models.
To calculate tree length more efficiently, Yves Pauplin proposed a formula that computes the total length of a tree using distance matrix directly, which avoid calculation of every individual branch. The 'direct calculation' (DC) method gives equal importance to both sides of every internal split. Unlike the OLS approach, which efficiently weight every taxon equally and can be biased toward clades with more taxa, Pauplin's method applies a 'balanced' weighting, which ensures two lineages descending from a node contributes equally to total length, regardless of number of species they contain.