Scuphr: A probabilistic framework for cell lineage tree reconstruction

Hazal Koptagel, Seong-Hwan Jun, Joanna Hård, Jens LagergrenPLOS Computational Biology 2024 · DOI

Introduction

Tracing the developmental history of cells is fundamental to understanding organismal growth and tissue maintenance. While lineage reconstruction is well-established in oncology due to the high mutational burden of tumors, healthy tissues present a significant challenge. In healthy cells, somatic mutations are rare—occurring at a rate of approximately one per billion base pairs per division. Scuphr (Single-cell probabilistic framework for cell lineage tree reconstruction) addresses this by providing a faster, more accurate method for mapping these "family trees" in healthy, diploid cells.

The Challenge: Noise in Single-Cell Sequencing

To detect rare mutations, researchers utilize single-cell DNA sequencing (scDNA-seq), which requires massive amplification of a single cell's genome. This process introduces two primary technical artifacts:

  1. Amplification Errors (AEs): Polymerase mistakes that mimic real mutations.
  2. Allelic Dropout (ADO): The failure of one allele to amplify, which can hide heterozygosity.

Existing methods often struggle to differentiate these artifacts from genuine somatic mutations, leading to inaccurate tree topologies.

Methodology

Scuphr employs a distance-based approach powered by a probabilistic graphical model. Unlike traditional methods that rely on computationally expensive Markov chain Monte Carlo (MCMC) simulations, Scuphr is designed for high-performance parallel computing.

The Scuphr workflow: (a) Input reads from bulk and single cells are analyzed for candidate mutations; (b) Pairwise distance matrices are calculated independently for each site; (c) Matrices are combined to reconstruct the lineage tree.

Key Technical Innovations

  • Artifact Modeling: Scuphr uses a generalized Pólya urn process to mathematically model DNA amplification, allowing it to account for the probability of AEs and ADO at each site.
  • Read-Phasing: This "secret sauce" leverages known germline heterozygous sites (gSNVs). By identifying which allele a candidate mutation resides on, Scuphr can distinguish true somatic mutations (which consistently appear on the same allele) from random sequencing errors.
  • Parallel Architecture: The framework calculates pairwise distances between cells for each genomic site independently. This "embarrassingly parallel" design allows the workload to be distributed across hundreds of CPU cores, dramatically reducing runtime.
  • Neighbor-Joining (NJ): The final tree topology is constructed using the standard NJ algorithm based on the aggregated distance matrices.

Key Insights: The Power of Phasing

The central innovation of Scuphr is the use of germline variation as a reference frame. In healthy diploid cells, a true somatic mutation will be physically linked to a specific parental allele.

Comparison of non-mutated and mutated alleles. Scuphr uses read-phasing to confirm if mutations consistently appear on the same phased allele, filtering out random noise.

By observing the phase of the reads, Scuphr can effectively filter out artifacts. If a "mutation" appears randomly across different alleles or lacks consistent phasing, the model assigns it a low probability of being a true somatic event.

Results and Performance

The authors validated Scuphr using both synthetic and biological datasets:

  • Synthetic Benchmarks: In simulations with high amplification error rates ($10^{-3}$), Scuphr achieved nearly double the accuracy of SCIF, the previous state-of-the-art method.
  • Computational Efficiency: Scuphr scales linearly with hardware. While a single core might take 1.6 hours for 1,000 sites, a modest cluster can process 100,000 sites in roughly one hour.
  • Biological Validation: When applied to a dataset of 18 human fibroblast cells, Scuphr successfully identified major clonal structures with high statistical support (0.8 Transfer Bootstrap Expectation), outperforming competing tools like Phylovar.

Discussion and Future Directions

While Scuphr represents a significant leap in efficiency and accuracy for healthy tissue, it has specific limitations. It currently focuses on tree topology rather than branch lengths (time/mutation counts). Furthermore, the model assumes a diploid genome, making it less suitable for cancer genomes characterized by complex Copy Number Variations (CNVs). Future iterations may incorporate CNV handling and reduce the dependency on bulk sequencing data by utilizing public SNP databases.

Summary updated

BibTeX
@article{koptagel2024scuphr,
  author = {Hazal Koptagel and Seong-Hwan Jun and Joanna Hård and Jens Lagergren},
  title = {{Scuphr: A probabilistic framework for cell lineage tree reconstruction}},
  journal = {PLOS Computational Biology},
  year = {2024},
  doi = {10.1371/journal.pcbi.1012094},
}
Figure