Minimum evolution

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.

Phylogenetic tree of Acantobasidium created using Minimum Evolution

A simplified description of the Minimum Evolution algorithm

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 Likelihood	Looks for the most probable function possible given data parameters	Large datasets where low bias is important	O(N), this improves with larger datasets
Unweighted Pair Group Method with Arithmetic Mean(UPGMA)	Creates a cluster of clusters and finds the arithmetic mean of the clusters	Initial examination of data	O(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(N³) 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(N³) 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

$L(T|D)=P(D|T,M)$

Maximum Likelihood differs from Minimum Evolution in the sense that it calculates likelihood $L(T|D)$, evaluating many different phylogenetic trees $T$ and selecting the one that maximizes the probability $P$ of observing the data $D$ under a substitution model $M$.

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 length of an internal branch (blue) is calculated using only the "local" distances between the four taxa or subtrees directly adjacent to it (labeled i, j and k, l)

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.

Building on Pauplin's work, Richard Desper and Olivier Gascuel formalized this approach as Balanced Minimum Evolution (BME). They proved that Pauplin's formula is a special, "balanced" case of WLS framework and demonstrated that BME successfully satisified the EDGE_LENGTHS property required for statistical consistency. Furthermore, they showed that the BME model ensures that branch lengths remain non-negative as long as the input distance satisfy the triangle inequality, which overcomes the limitation of the original OLS models. Desper and Gascuel initially demonstrated the power of this approach through their software, FastME. Their preliminary simulations suggested that the BME principle was more accurate than, or at least equivalent to, all ther distance-based methods available at the time, while maintaining a running time significantly faster than the popular Neighbor-Joining (NJ) algorithm.

This claim of efficiency and accuracy was confirmed by Le Sy Vinh and Arndt von Haeseler. Through massive and systematic simulation experiments, they showed that the accuracy of the ME criterion under the BME branch length estimation model is by far the highest in distance-based methods and not inferior to those of alternative criteria based on Maximum Likelihood or Bayesian Inference.

Moreover, as shown by Daniele Catanzaro, Martin Frohn and Raffaele Pesenti, the minimum length phylogeny under the BME branch length estimation model can be interpreted through information theory as a (Pareto optimal) consensus tree that minimizes entropy across the entire evolution history. This particular information theory-based interpretation is conjectured to be shared by all distance methods in phylogenetics.

Advantages and Disadvantages

Advantages

Computational Efficiency

Minimum Evolution (ME) is computationally more efficient than character-based methods such as Maximum Likelihood (ML), making it better suited to large datasets with multiple sequences. This efficiency is clear when ME is implemented using Neighbor-Joining (NJ), which has been shown to almost always outperform other algorithms in inferring the tree. In comparison, ML requires extensive searches, resulting in long computational times. This computational advantage makes ME more suitable for large datasets or for exploratory analyses that require many bootstrap replicates, which would make ML too slow to use.

Theoretically Unbiased

Minimum Evolution (ME) is theoretically unbiased, meaning it doesn’t favor incorrect trees when evolutionary distances are used. Rzhetsky and Nei have shown through studies that the ME method doesn’t suffer from either of the 2 problems that affect other least-squares (OLS) methods:

1. The OLS criterion can be biased and may select an incorrect tree more often than expected under random selection when evolutionary distances are large.
2. Generalized least-squares (GLS) methods may not be applicable when distances are too small.

The ME criterion avoids these biases and issues that may hurt other algorithms, making it unbiased and consistent for phylogenetic tree generation when distances are present.

Statistically Consistent

Minimum evolution assumes that the tree with the smallest total branch-length estimate is the most likely representation of evolutionary history. As the sequence lengths increase, the ME method tends to recover the true evolutionary tree, provided the evolutionary distances used are statistically unbiased.

Disadvantages

Time Complexity

Minimum Evolution (ME) has a time complexity of NP-hard. This means that as more taxa/sequences are added, the time to find the optimal ME tree grows exponentially, making very large datasets take a long time. Although ME is very time consuming heuristic ME is efficient. As the amount of sequences increases (n is increased) the amount of trees increases exponentially. The formula below proves that as you add more sequences, the number of possible trees grows faster than exponentially. Since minimum evolution requires evaluating the tree length for each potential tree, more sequences means more trees to search, which forces an exhaustive search to examine every single tree.

Number of unrooted trees for n taxa = (2n−5)! / [2ⁿ⁻³ (n−3)!]  

Performance on Distant Data

Saturation results in underestimation of the actual evolutionary differences between sequences. Therefore, Minimum Evolution is vulnerable to the long branch attraction effect in which quickly evolving or deeply diverged sequences are falsely combined to reduce the length of the phylogenetic tree.

Algorithmic aspects

The core computational challenge of minimum evolution is finding the tree with the minimum total branch length across all possible tree topologies. Even for moderate numbers of taxa, the number of possible trees grows super-exponentially, making exhaustive search infeasible. The "minimum evolution problem" (MEP) is formally NP-hard, meaning no efficient exact algorithm is known to exist. The "balanced minimum evolution problem" (BMEP), which applies the stricter BME criterion, is even harder to approximate: it is APX-hard, meaning that beyond a certain threshold, no polynomial-time algorithm can guarantee an arbitrarily close approximation to the true optimum unless P = NP.

A number of exact algorithms solving BMEP have been described. The best known exact algorithm remains impractical for more than a dozen taxa, even with multiprocessing. There is only one approximation algorithm with proven error bounds, published in 2012.

In practical use, BMEP is overwhelmingly implemented by heuristic search. The basic, aforementioned neighbor-joining algorithm implements a greedy version of BME.

FastME, the "state-of-the-art", starts with a rough tree then improves it using a set of topological moves such as Nearest Neighbor Interchanges (NNI). Compared to NJ, it is about as fast and more accurate.

FastME (Fast Minimum Evolution) operates on the Balanced Minimum Evolution (BME) principle, introduced by Desper and Gascuel in 2002. Unlike OLS-based ME (where branch lengths are fitted by ordinary least squares, treating all pairwise distances as equally reliable), the BME scheme assigns topology-dependent weights to pairwise distances such that sibling subtrees contribute equally, regardless of the number of taxa they contain. This balanced weighting is derived from Pauplin's branch length estimation formula, in which the tree length is expressed analytically as:

$L=\sum _{i<j}2^{1-p_{ij}}\cdot \delta _{ij}$

where $\delta _{ij}$ is the estimated evolutionary distance between taxa $i$ and $j$, and $p_{ij}$ is the topological distance (i.e., the number of branches on the path) between $i$ and $j$ in tree $T$. The weight $2^{1-p_{ij}}$ decreases exponentially with topological separation, so that closely related taxa pairs receive greater weight in the tree length calculation. Desper and Gascuel proved that this BME tree length is equivalent to a weighted least-squares estimator with variances proportional to $2^{p_{ij}}$, making it the minimum-variance tree length estimator under those assumptions.

A key computational advantage of BME is that evaluating a nearest neighbor interchange (NNI) requires only local recalculation. For a tree with four subtrees A, B, C, D around an internal edge, swapping subtrees B and C changes the tree length by:

$\Delta L=\delta _{AC}^{T}+\delta _{BD}^{T}-\delta _{AD}^{T}-\delta _{BC}^{T}$

where $\delta _{XY}^{T}$denotes the balanced average distance between subtrees X and Y. This formula allows FastME to evaluate each NNI in constant time per swap once the balanced averages have been computed.

The algorithm proceeds in two stages. In the first stage, a greedy minimum evolution (GME) algorithm constructs a starting topology in $O(n^{2})$ time by iteratively inserting taxa at the position that minimizes the BME tree length. In the second stage, the topology is refined using NNI moves (and optionally subtree prune and regraft (SPR) moves), with the total cost of $p$ NNI operations being $O(n^{2}+pn)$. Since $p$ is typically much smaller than $n$, the overall complexity is $O(n^{2})$ in practice, which is faster than the $O(n^{3})$ cost of standard NJ. A further theoretical advantage is that any tree that is a local minimum under the BME-NNI search is guaranteed to have all positive branch lengths, provided the input distances satisfy the triangle inequality—a property that NJ and related methods do not share.

Pseudocode of the FastME algorithm:

Input: Distance matrix D for n taxa
Output: Tree T with locally minimal BME score

Phase 1 — Greedy Minimum Evolution (GME) tree construction:
  1. Initialize tree T with the first three taxa
  2. For each remaining taxon t (from taxon 4 to n):
     a. For each edge e in current tree T:
        i.  Compute the change in BME tree length if t is inserted at e
     b. Insert t at the edge that yields the smallest BME tree length
     (Total cost: O(n^2))

Phase 2 — Topology refinement via Balanced NNI (BNNI):
  3. Repeat until no improvement is found:
     a. For each internal edge e in T with subtrees A, B, C, D:
        i.   Compute ΔL = δ_AC + δ_BD − δ_AD − δ_BC
             (balanced average distances between the four subtrees)
        ii.  If ΔL < 0, perform the NNI swap and update T
     b. If any swap was performed, restart the scan
     (Total cost: O(n^2 + p·n), where p = number of swaps)

Phase 3 (optional) — SPR refinement:
  4. For each possible SPR move on T:
     a. Prune a subtree and regraft it at each candidate edge
     b. Evaluate the resulting BME score
     c. If the score improves, accept the move and update T
  5. Repeat until no SPR move improves the score

  Return final tree T

Simulations reported by Desper and Gascuel demonstrate that FastME consistently outperforms NJ in terms of topological accuracy, particularly when evolutionary rates vary or distances deviate from strict additivity. It has also been successfully used on datasets with over 1,000 taxa.

Like most distance-based methods, BME assumes that the input distances are additive. When this assumption does not hold—due to noise, unequal rates, or other violations—the resulting trees may still be close to optimal, but accuracy can be affected. In addition to FastME, metaheuristic methods such as genetic algorithms and simulated annealing have also been used to explore tree topologies under the minimum evolution criterion, particularly for very large datasets where traditional heuristics may struggle.

See also

• Least squares inference in phylogeny
• Occam's razor

Further reading

• Catanzaro D, Pesenti R, Wolsey L (2020). "On the Balanced Minimum Evolution Polytope". Discrete Optimization. 36 100570. doi:10.1016/j.disopt.2020.100570. hdl:2078.1/230413. S2CID 213389485.