HERACLES for fast and accurate likelihood-based reconstruction of massive lineages

Abstract

CRISPR-based lineage recording technologies can trace the ancestry of hundreds of thousands of cells, yet reconstructing accurate phylogenies at this scale remains computationally challenging. Likelihood-based methods employ explicit evolutionary models of CRISPR editing that improve tree accuracy but require computationally expensive searches over tree topologies, whereas distance-based alternatives scale efficiently but rely on distances that may not faithfully represent the editing process, introducing biases whose magnitude and direction are unknown. Here, we introduce HERACLES, which optimizes cell coordinates in hyperbolic space under a quartet-based composite likelihood of CRISPR editing. By recovering local branching structures directly from embedded distances, HERACLES guides continuous optimization with an explicit evolutionary model without repeatedly constructing and evaluating complete phylogenies. Across simulated benchmarks, HERACLES improves reconstruction accuracy over existing methods and scales to lineages containing 150,000 cells in about four hours on a single GPU. On experimental KP-tracer and PEtracer datasets, HERACLES reconstructs phylogenies consistent with independent anatomical annotations and temporal lineage markers. Its flexible likelihood framework also accommodates different recording mechanisms: incorporating sequential editing improves reconstruction of simulated DNA Typewriter lineages. Together, these results establish continuous optimization of local evolutionary relationships as a scalable and flexible approach to probabilistic lineage reconstruction.