Parallel and scalable balanced minimum evolution algorithm for large-scale phylogenetic inference

Abstract

The rapid growth of biological data demands scalable yet robust phylogenetic methods. Distance-based approaches are widely adopted not only in alignment-based molecular phylogenetics but also in emerging applications involving alternative distance measures. Balanced minimum evolution (BME) is an important principle in distance-based phylogenetic inference. A heuristic for BME using a taxon addition strategy was developed and provided by the FastME package, producing accurate tree topologies compared with alternative methods. However, beyond the original FastME implementation, there has been little development aimed at scaling this algorithm to the size of modern datasets. We present a significantly redesigned implementation of the BME algorithm that substantially improves computational efficiency while preserving mathematical equivalence. The key algorithmic improvement is the replacement of recursive tree traversal with flattened, incrementally growing arrays representing tree topology, traversal order and node properties. This design reduces traversal overhead, improves memory locality, and enables parallelization of the BME algorithm for the first time. Benchmarks show that our implementation delivers multiple dozen-fold speedup while consuming half the memory of FastME on datasets with tens of thousands of taxa. It can effectively analyze datasets of over 100,000 taxa, which are prohibitive with FastME. In addition, this implementation compares favorably in both efficiency and solution quality with a modern implementation of neighbor joining (NJ), an alternative BME heuristic using an agglomerative clustering strategy. Our BME algorithm has been released as part of the open-source Python library scikit-bio. It substantially broadens access to BME-based phylogenetic inference at scale.