DartUniFrac: Approximate UniFrac via Weighted MinHash

By reinvestigating the mathematical properties of UniFrac, we prove that it can be reformulated into an elegant equivalent form that enables substantially more efficient computation. This reformulation unlocks the use of cutting-edge MinHash-like sketching algorithms (for example, those deployed at web scale for large-scale similarity comparisons) together with succinct data structures (such as balanced-parentheses representations of trees). These ingredients lead to a new UniFrac algorithm—DartUniFrac—and a near-optimal, hardware-optimized implementation that leverages SIMD and GPUs and is more than three orders of magnitude faster than the state-of-the-art.