Ultrafast and ultralarge distance-based phylogenetics using DIPPER

Distance-based methods are commonly used to reconstruct phylogenies for various applications owing to their excellent speed, scalability and theoretical guarantees. However, classical de novo algorithms are hindered by cubic time and quadratic memory complexity, making them impractical for emerging datasets containing millions of sequences. Here we present DIPPER, a distance-based tool for phylogenetic reconstruction on graphics processing units (GPUs), designed to maintain high accuracy and a low memory footprint. DIPPER employs a divide-and-conquer strategy, a placement strategy and an on-the-fly distance calculator that improve runtime and memory complexity to O(N.log(N)) and O(N), respectively, with N taxa. DIPPER also maintains a low memory footprint on the GPU that is independent of the number of taxa. DIPPER outperforms existing methods in speed and memory efficiency on both simulated and real-world datasets, enabling the reconstruction of 10 million sequences in under 7 h on a single NVIDIA RTX A6000 GPU.