PhyloSOLID: Robust phylogeny reconstruction from single-cell data despite inherent error and sparsity

Abstract While lineage tracing based on somatic mutations in single-cell sequencing data offers a powerful approach to reconstructing cellular histories in vivo, its reliability is fundamentally limited by pervasive technical artifacts—specifically, high error rates and data sparsity. These issues introduce false phylogenetic signals that corrupt tree topology and lead to spurious evolutionary conclusions. To overcome these limitations, we present PhyloSOLID, a phylogenetic algorithm designed to be inherently robust to these data imperfections. PhyloSOLID employs a progressive scaffolding strategy that begins with graph-based construction of a low-resolution, high-confidence backbone tree from reliable and uniformly covered mutations. This scaffold is then refined through the iterative integration of remaining data, guided by a Bayesian statistical model that penalizes phylogenetic inconsistencies to effectively separate the true evolutionary signal from technical artifacts. Benchmarking on both simulated datasets and multiple ground-truth datasets demonstrates that PhyloSOLID achieves superior lineage reconstruction accuracy over existing methods, for both single-cell RNA-seq and DNA-seq data. Additionally, a user-friendly web interface enables customized quality assessment, artifact removal, and interpretation of lineage structures. PhyloSOLID provides a powerful solution for decoding cellular evolution in developmental and disease contexts.