HERACLES for fast and accurate likelihood-based reconstruction of massive lineages
- 1Memorial Sloan Kettering Cancer Center
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.
Related
- Accurate MAG reconstruction from a complex soil microbiome through combined short- and HiFi long-reads metagenomics
- Scale-dependent associations between genetic similarity and aggregation behaviour in three toad lineages
- Cell-cycle inhibition preserves robust development but rebalances lineages in mouse gastruloids
- Single-cell transcriptomics of enriched rare neural lineages of Tribolium castaneum
- Genome-wide analyses resolve three clonal lineages and lineage-specific ploidy in Phytophthora cinnamomi
BibTeX
@misc{persad2026heracles,
title = {{HERACLES for fast and accurate likelihood-based reconstruction of massive lineages}},
author = {S. C. Persad and Q. Morris},
howpublished = {bioRxiv},
year = {2026},
month = nov,
doi = {10.64898/2026.11.06.764882},
url = {https://www.biorxiv.org/content/10.64898/2026.11.06.764882v1},
note = {CC BY},
}
RIS
TY - UNPB
TI - HERACLES for fast and accurate likelihood-based reconstruction of massive lineages
AU - S. C. Persad
AU - Q. Morris
PY - 2026
DA - 2026/11/06
PB - bioRxiv
DO - 10.64898/2026.11.06.764882
UR - https://www.biorxiv.org/content/10.64898/2026.11.06.764882v1
AB - 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.
ER -