scLongTree: an accurate computational tool to infer the longitudinal tree for scDNAseq data

The paper introduces scLongTree, a scalable and accurate computational tool designed to infer subclonal evolutionary trees from longitudinal single-cell DNA sequencing data, demonstrating superior performance over existing methods on both simulated and real-world cancer datasets.

The Gist

Imagine you are trying to solve a massive, messy family reunion photo album, but with a twist: the people in the photos are cancer cells, and the "family history" is how the cancer grew and changed over time.

This paper introduces a new digital detective tool called scLongTree. Its job is to figure out the exact family tree of a tumor using data from single-cell DNA sequencing.

Here is the story of why this tool was needed, how it works, and why it's a game-changer, explained through simple analogies.

The Problem: The "Blurry" and "Time-Traveling" Puzzle

1. The Old Way (Single Time Point):
Imagine you walk into a room and take a snapshot of 100 people. You try to guess who is related to whom based only on that one picture. It's hard because you don't know who arrived first, who left, or who changed their clothes in the middle.

• In science: Most tools look at cancer cells from just one moment in time. They try to guess the order of mutations (genetic changes) but often get confused because they lack the timeline.

2. The New Data (Longitudinal):
Now, imagine you take photos of the same room at 9:00 AM, 12:00 PM, and 3:00 PM. You can see exactly who arrived when, who left, and how the group evolved.

• In science: Scientists now have data from cancer cells taken at multiple time points (e.g., before treatment, during treatment, and after relapse). This is a goldmine of information, but the existing tools were too clumsy to use it.

3. The Messy Data:
Single-cell DNA sequencing is like trying to read a book where some pages are torn out, some words are smudged, and some letters are accidentally added.

• The Challenge: The data has "False Positives" (seeing a mutation that isn't there) and "False Negatives" (missing a mutation that is there). Previous tools struggled to clean up this mess, especially when the family tree got too big (hundreds of mutations) or too complex.

The Solution: scLongTree

scLongTree is a new computer program designed specifically to handle these "time-traveling" photos. Think of it as a smart, time-aware family tree builder.

Here is how it works, step-by-step:

1. Grouping the Clues (Clustering)

First, the tool looks at the cells at each specific time point (9 AM, 12 PM, 3 PM) and groups them into "families" (subclones) based on their genetic makeup.

• Analogy: It's like sorting a pile of mixed-up LEGO bricks by color and shape at each hour of the day.

2. Cleaning the Noise (Removing Fake Families)

Sometimes, the tool might accidentally create a tiny, fake family group just because of a smudge in the data. scLongTree is smart enough to ask, "Does this tiny group actually make sense in the big picture?"

• The Trick: If removing a tiny group makes the whole family tree look more logical and less messy, scLongTree deletes that fake group. It acts like an editor cutting out the bad sentences from a story to make the plot clearer.

3. Filling in the Gaps (The "Ghost" Ancestors)

This is the tool's superpower. Imagine you have a photo of a grandfather at 9 AM and his grandson at 3 PM, but you have no photo of the father in between.

• Old tools would just draw a line from Grandpa to Grandson, guessing the father's traits.
• scLongTree says, "Wait, there must be a father in between!" It invents a "Ghost Node" (an unobserved ancestor) to connect the dots logically. It fills in the missing chapters of the cancer's history that were skipped over because we didn't take a sample at that exact moment.

4. Fixing the Rules (The k-Dollo Model)

In nature, some genetic changes happen once and never go back (like a broken bone), while others can flip back and forth.

• The Rule: scLongTree follows a rule called k-Dollo. It assumes that a specific mutation usually happens only once (like a unique tattoo), but it can disappear a few times (like a tattoo fading).
• The Correction: If the tool sees the same mutation appearing in two different branches (which shouldn't happen often), it fixes the tree to make sure the mutation only happened once, unless the evidence says otherwise.

Why is this better than the others?

The authors tested scLongTree against other famous tools (like LACE, SCITE, and SiCloneFit) using both fake data (simulations) and real patient data.

1. It's Stronger with Big Data:

   • Analogy: Imagine trying to solve a puzzle with 50 pieces vs. 500 pieces.
   • Result: When the puzzle got huge (hundreds of mutations), the old tools (like LACE) gave up and stopped working. scLongTree kept going, solving puzzles with thousands of cells and hundreds of mutations in just a few hours.

2. It's More Robust:

   • Analogy: If you add a few extra, confusing pieces to a puzzle, a good solver ignores them. A bad solver gets confused and changes the whole picture.
   • Result: When the researchers added more mutations to the real cancer data, the old tool (LACE) changed its mind about the family tree completely. scLongTree stayed consistent, proving it doesn't get confused by extra noise.

3. It Sees the "Invisible":

   • scLongTree was the only one that could successfully guess the existence of the "Ghost Ancestors" (the unobserved cells between time points), making the history of the cancer much more accurate.

The Real-World Impact

The researchers tested this on two real cancer cases:

1. Breast Cancer (SA501): They reconstructed the history of a tumor growing over time. scLongTree confirmed the known history and showed it could handle more data without getting confused.
2. Leukemia (AML107): They used it on a massive dataset with over 4,000 cells. The tool successfully mapped out the evolution of the leukemia, showing it can handle huge, complex datasets that other tools can't touch.

The Bottom Line

scLongTree is like a high-tech, time-traveling genealogist for cancer. It takes messy, incomplete snapshots of cancer cells taken at different times, cleans up the errors, fills in the missing family members, and draws a clear, accurate map of how the cancer grew.

This helps doctors understand:

• How the cancer evolved.
• When dangerous mutations appeared.
• Why a treatment might have failed (because a new branch of the family tree grew).

Ultimately, this tool helps scientists design better treatments by understanding the true "family tree" of the disease.

Technical Summary

1. Problem Statement

Context: Cancer evolution is driven by somatic mutations, leading to intra-tumor heterogeneity (ITH). Reconstructing the evolutionary history of tumor cells via a subclonal tree is crucial for understanding cancer progression, prognosis, and treatment.
Limitations of Current Tools:

• Single-Time-Point Bias: Most existing tools (e.g., SCITE, SiCloneFit, SiFit) assume data is collected at a single time point. They fail to utilize temporal information, which is critical for resolving mutation order, inferring unobserved intermediate nodes, and tracking clonal dynamics.
• Scalability Issues: The only existing tool designed for longitudinal data, LACE, relies on Monte Carlo Markov Chain (MCMC) to solve a Boolean matrix factorization problem. It is computationally prohibitive for datasets with hundreds of mutations (often failing to run within 24 hours for >140 mutations) and cannot reconstruct unobserved subclones that existed between sampling time points.
• Data Noise: Single-cell DNA sequencing (scDNA-seq) data is noisy, containing false positives (FP), false negatives (FN), missing entries, and doublet errors.

Goal: Develop a scalable, accurate computational tool that infers longitudinal subclonal trees from multi-time-point scDNA-seq data, capable of handling hundreds of mutations and thousands of cells while reconstructing unobserved evolutionary intermediates.

---

2. Methodology

scLongTree employs a combinatorial approach integrated with statistical refinement. The pipeline consists of five main steps:

A. Cell Clustering (Time-Point Specific)

• Input: A cell-by-mutation matrix where each cell is tagged with a specific time point.
• Algorithm: Uses BnpC (a Bayesian non-parametric clustering tool) to cluster cells independently at each time point.
• Rationale: Clustering per time point allows for the independent estimation of time-specific error rates (FP/FN) and prevents the mis-clustering of subclones that differ slightly but appear at different times.
• Stability: The tool runs BnpC five times to account for its non-deterministic nature, selecting the best run later.

B. Elimination of Spurious Clusters

• Problem: BnpC may over-cluster, creating small, non-bona fide subclones.
• Process:
  1. Clusters are ranked by posterior probability.
  2. Starting from the lowest probability, the algorithm tests if removing a cluster improves the overall tree probability and keeps FP/FN rates within acceptable bounds.
  3. If a cluster is deemed spurious, its cells are reassigned to other clusters via maximum likelihood (Eq. 3), and the tree is re-inferred.
  4. This iterative process continues until all clusters are validated.

C. Longitudinal Tree Inference (Combinatorial Approach)

• Core Innovation: Unlike LACE's MCMC, scLongTree uses a fast, deterministic combinatorial algorithm.
• Unobserved Nodes: The algorithm explicitly infers unobserved nodes (intermediate subclones) between consecutive time points ($p$ and $p+1$).
  • It constructs a hash table of mutations shared by nodes in $p+1$.
  • It identifies the largest set of mutations shared by the largest set of nodes in $p+1$ that are not present in $p$.
  • It inserts an unobserved node between $p$ and $p+1$ to connect them, minimizing parallel mutations.
• Model: Adheres to the $k$-Dollo model, which assumes infinite sites (no parallel mutations) but allows up to $k$ back mutations (loss of mutations), accounting for copy number losses.

D. Correction of Parallel and Back Mutations

• Post-Processing: After tree construction, the tool refines mutation assignments using $k$-Dollo constraints.
  • Parallel Mutations: If a mutation appears on multiple edges, the algorithm calculates likelihood ratios to assign the mutation to the single most probable edge.
  • Back Mutations: If a mutation is lost on more than $k$ edges, the algorithm selects the $k$ edges with the highest likelihood of loss to retain the loss event, removing it from others.
• Output: A refined tree with corrected mutation placements and updated FP/FN rates.

E. Optimal Clustering Selection

• The tool evaluates the five BnpC runs based on final FP/FN rates (removing outliers) and selects the run with the highest tree support score (product of posterior probabilities of all nodes).

---

3. Key Contributions

1. First Scalable Longitudinal Tool: Introduces scLongTree, the first tool capable of inferring longitudinal trees for datasets with hundreds of mutations and thousands of cells (unlike LACE, which fails at scale).
2. Unobserved Node Reconstruction: uniquely capable of inferring intermediate subclones that were not sequenced but existed between sampling time points, filling gaps in evolutionary history.
3. Robustness to Mutation Count: Demonstrates high accuracy and consistency regardless of the number of mutations used, whereas competitors (like LACE) show structural instability when mutation counts increase.
4. Combinatorial Efficiency: Replaces computationally expensive MCMC with a fast combinatorial algorithm, enabling analysis of large datasets within hours.
5. Statistical Rigor: Integrates Bayesian clustering, iterative spurious cluster elimination, and $k$-Dollo constraints to handle scDNA-seq noise effectively.

---

4. Results

Simulation Studies

• Accuracy: scLongTree outperformed state-of-the-art tools (LACE, SCITE, SiCloneFit, RobustClone) in pairwise SNV accuracy across six variables (FP rate, FN rate, missing rate, unobserved node frequency, error variance, and mutation count).
• Scalability:
  • LACE: Failed to complete runs within 24 hours when mutation counts exceeded ~140.
  • scLongTree: Successfully processed datasets with up to 140 mutations and 1,000 cells in a few hours.
• Unobserved Nodes: scLongTree achieved high F1 scores in detecting unobserved nodes, significantly improving phylogenetic accuracy (Robinson-Foulds distance) compared to methods that ignore them.
• Clustering: Incorporating tree information to refine clustering (via the elimination step) yielded higher V-measures than BnpC or SCG alone.

Real Data Validation

• SA501 (Triple-Negative Breast Cancer):
  • Using 20 variants, scLongTree reproduced the known evolutionary tree (matching LACE and biological ground truth).
  • Robustness Test: When expanded to 55 variants, scLongTree maintained the exact same tree topology. In contrast, LACE produced a different, incorrect topology (misplacing variants 0 and 7), demonstrating that scLongTree is robust to the number of input mutations.
• AML107 (Acute Myeloid Leukemia):
  • Applied to a dataset with 4,617 cells (2,817 at diagnosis, 1,800 at relapse).
  • Successfully reconstructed the evolutionary tree, correctly identifying the temporal order of driver mutations ($TP53$ early, $DNMT3A$ later), confirming scalability to thousands of cells.

---

5. Significance and Future Directions

Significance:

• Clinical Impact: Provides a more accurate view of tumor evolution over time, which is essential for understanding treatment resistance and relapse mechanisms.
• Methodological Advance: Solves the scalability bottleneck of longitudinal phylogenetic inference, making it feasible to analyze large-scale clinical scDNA-seq datasets.
• Biological Insight: The ability to infer unobserved nodes allows researchers to reconstruct "missing links" in cancer evolution, offering a more complete picture of how subclones diverge between sampling points.

Future Directions:

• Joint Inference: Combining clustering and tree inference into a single step to potentially improve accuracy, despite increased computational complexity.
• Allele Dropout (ADO) Modeling: Integrating specific models for ADO regions to further reduce false negative rates.
• Non-Consecutive Time Points: Extending the algorithm to link subclones across non-consecutive time points (e.g., $p$ to $p+2$) if $p+1$ is missing.
• Regularization: Adding explicit regularization terms to prevent overfitting in noisy datasets with limited observations.

Availability: The tool is open-source and available at https://github.com/compbio-mallory/sc_longitudinal_infer.