Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle

TLDR

The Minimum Evolution approach is statistically consistent with ordinary least‑squares fitting, but traditionally it starts from a Neighbor‑Joining topology and then performs a topological search. This study investigates a greedy Minimum Evolution strategy that constructs an initial topology in O(n²) time. The algorithm builds the starting tree in O(n²) time, then searches for the optimal topology using nearest‑neighbor interchanges with a cost of O(n² + p n), and also evaluates a balanced weighting scheme that requires O(n² × diam(T)) for tree construction and O(p n × diam(T)) for NNIs, which remains practical because the expected diameter is O(log n). The Greedy Minimum Evolution algorithm combined with NNIs produces trees nearly as accurate as Neighbor‑Joining, while the balanced Minimum Evolution scheme markedly improves topological accuracy over Neighbor‑Joining and other distance‑based methods, especially for large trees.

Abstract

The Minimum Evolution (ME) approach to phylogeny estimation has been shown to be statistically consistent when it is used in conjunction with ordinary least-squares (OLS) fitting of a metric to a tree structure. The traditional approach to using ME has been to start with the Neighbor Joining (NJ) topology for a given matrix and then do a topological search from that starting point. The first stage requires O(n3) time, where n is the number of taxa, while the current implementations of the second are in O(p n3) or more, where p is the number of swaps performed by the program. In this paper, we examine a greedy approach to minimum evolution which produces a starting topology in O(n2) time. Moreover, we provide an algorithm that searches for the best topology using nearest neighbor interchanges (NNIs), where the cost of doing p NNIs is O(n2 + pn), i.e., O(n2) in practice because p is always much smaller than n. The Greedy Minimum Evolution (GME) algorithm, when used in combination with NNIs, produces trees which are fairly close to NJ trees in terms of topological accuracy. We also examine ME under a balanced weighting scheme, where sibling subtrees have equal weight, as opposed to the standard "unweighted" OLS, where all taxa have the same weight so that the weight of a subtree is equal to the number of its taxa. The balanced minimum evolution scheme (BME) runs slower than the OLS version, requiring O(n2 × diam(T)) operations to build the starting tree and O(pn × diam(T)) to perform the NNIs, where diam(T) is the topological diameter of the output tree. In the usual Yule-Harding distribution on phylogenetic trees, the diameter expectation is in log(n), so our algorithms are in practice faster that NJ. Moreover, this BME scheme yields a very significant improvement over NJ and other distance-based algorithms, especially with large trees, in terms of topological accuracy.