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

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.