HERACLES skips the tree search: quartet likelihoods rebuild a 150,000-cell lineage in about four hours on one GPU
Synopsis
CRISPR lineage recorders can trace the ancestry of hundreds of thousands of cells, but likelihood-based tree building searches over tree topologies and becomes impractical at that scale. HERACLES places each cell as a point in hyperbolic space, scores the CRISPR editing likelihood of sampled cell quartets, and optimizes those coordinates by gradient descent before a single neighbour-joining pass yields the full tree. On simulated benchmarks its reconstruction error is lower than LAML, Startle-NNI and distance-based methods, and it handles 150,000 cells in about four hours on one GPU.
Interpretation
Lineage reconstruction can now use an explicit evolutionary model without repeatedly building and scoring complete phylogenies, bringing likelihood-based accuracy to the hundred-thousand-cell scale. Exact methods previously ran exhaustive or stochastic searches over tree space, which grows super-exponentially with cell count, while greedy neighbour joining, UPGMA and Cassiopeia-Greedy are fast but rely on distances that need not faithfully represent the true tree. Mean reconstruction error was lowest across all eight conditions of the LAML benchmark, and the advantage grew with lineage size, from ΔRF = −0.023 at 250 cells to ΔRF = −0.12 at 500–1,000 cells; at those larger sizes LAML's topology search returned its neighbour-joining starting tree unchanged in 146 of 150 datasets.
The method puts cells in hyperbolic space so that distances between them play the role of evolutionary distances, then moves those coordinates using the likelihood of sampled quartets. Hyperbolic space accommodates exponential branching with low distortion, but earlier pairwise-likelihood embeddings do not constrain shared branching structure, and embedding methods that rebuild a full tree at each step cost at least quadratically in cell count. Each quartet needs only six pairwise hyperbolic distances plus distances to the founder to recover a rooted topology and branch lengths, and 15n quartets are sampled per iteration, making each likelihood step O(n×S); across 240 independently simulated datasets of 1,000–10,000 cells, HERACLES reduced mean RF distance by 0.14–0.15 and 0.10–0.12 relative to neighbour joining and UPGMA, outperforming both on 240/240 datasets.
Perspective
The demonstrated scope is reconstruction accuracy and scale on simulated benchmarks, plus two experimental datasets: 1,461 cells from KP-tracer tumour 3724_NT_All and 3,108 cells from PEtracer clone 4. These experimental datasets have no known true phylogeny, so they are checked only against anatomical sampling locations and independent lentiviral barcodes.
The quartet composite likelihood approximates the likelihood of the full phylogeny, and neighbourhood sampling does not guarantee coverage of every ancestral branch; KP-tracer migration counts depend on whether branches without edit support are collapsed, and without collapsing LAML needs slightly fewer total migrations than HERACLES (99 versus 101); HERACLES currently returns a single phylogeny without quantifying uncertainty.