DIPPER: DIstance-based Phylogenetic PlacER

We present DIPPER, a novel distance-based phylogenetic tool for ultrafast and ultralarge phylogenetic reconstruction on GPUs, designed to maintain high accuracy and a small memory footprint. DIPPER introduces several novel innovations, including a divide-and-conquer strategy, a placement strategy, and an on-the-fly distance calculator that greatly improve the runtime and memory complexity. These allow DIPPER to achieve runtime and space complexity of O(N.log(N)) and O(N), respectively, with N taxa. With divide-and-conquer, DIPPER is also able to maintain a low memory footprint on the GPU, independent of the number of taxa. DIPPER consistently outperforms existing methods in speed, accuracy, and memory efficiency, and scales to tree sizes 1–2 orders of magnitude beyond the limits of existing tools. With the help of a single NVIDIA RTX A6000 GPU, DIPPER is able to reconstruct a phylogeny from 10 million unaligned sequences in under 7 hours, making it the only distance-based method to operate at this scale and efficiency.