Identifying Robust Subclonal Structures through Tumor Progression Tree Alignment

This paper introduces omlta, an NP-hard algorithm for computing the optimal multi-label tree alignment to compare tumor clonal trees by minimizing removed mutation labels, and validates its application on non-small cell lung cancer and melanoma datasets.

The Gist

Imagine you are trying to reconstruct the family history of a massive, chaotic family reunion. In the world of cancer, this "family" is a tumor, and the "family members" are groups of cells called clones. Over time, these cells mutate, branch off, and evolve, creating a complex "family tree" of the tumor's growth.

Scientists use special software to draw these trees based on genetic data. But here's the problem: just like two different historians might draw slightly different family trees for the same family (one might miss a cousin, another might place an uncle in the wrong spot), different computer programs often produce different trees for the same tumor.

This paper introduces a new tool called omlta (pronounced like "om-lah-tah") to solve this confusion. Think of omlta as a "Super-Editor" or a "Tree-Matching Detective."

The Problem: Two Different Maps

Imagine you have two maps of the same city drawn by different cartographers.

• Map A says the library is on the left of the park.
• Map B says the library is on the right of the park.

If you try to compare them directly, they look totally different. You can't tell which map is "right" or if they are actually describing the same city. In cancer research, if the trees don't match, doctors can't be sure which mutations are driving the cancer or how it will spread.

The Solution: The "Super-Editor" (omlta)

The omlta tool doesn't just say "these trees are different." Instead, it acts like a clever editor who says: "Okay, let's find the parts of these two maps that do agree, and ignore the parts that are just noise or mistakes."

It does this by performing a specific operation: removing the minimum number of "labels" (mutations) from both trees until the remaining structures are identical.

• If Map A has a "Library" and Map B has a "Library" in the same spot, omlta keeps them.
• If Map A has a "Bakery" that Map B doesn't have, or if they disagree on where the "School" is, omlta temporarily "erases" those confusing parts from both maps to see the underlying structure that matches.

The result is a Consensus Tree—a "Gold Standard" version that represents the parts of the tumor's history that are undeniably real and robust, regardless of which computer program you used to draw it.

How It Works (The Analogy)

Think of the trees as two different versions of a story about a hero's journey.

• Story A: The hero fights a dragon, then a wizard, then a giant.
• Story B: The hero fights a giant, then a dragon, then a wizard.

If you just compare them, they seem totally different. But omlta looks deeper. It realizes that "Dragon" and "Giant" are both monsters, and the order might be a matter of perspective. It strips away the confusing details (the specific order of the fights) to find the core structure: "The hero fought three major enemies."

In the paper, the authors tested this on real cancer data:

1. Lung Cancer: They looked at 126 patients. They found that for some types of lung cancer, the computer programs disagreed a lot (the maps were very different). omlta helped them realize that these disagreements often happened when the cancer cells were very "noisy" or hard to read.
2. Melanoma: They compared trees made from different types of data (like looking at the whole forest vs. looking at individual leaves). omlta successfully found the common ground, proving that even with messy data, the core family tree of the cancer could be identified.

Why This Matters

In the past, if two computer programs gave different answers about a tumor, doctors were stuck. They didn't know which one to trust.

With omlta, doctors and scientists can now:

• Find the Truth: Identify the parts of the tumor's history that everyone agrees on.
• Spot the Noise: Realize that if the trees disagree, it might be because the data is messy, not because the biology is confusing.
• Better Treatments: By knowing exactly which mutations are stable and shared across different analyses, doctors can design better combination therapies to target the specific "branches" of the cancer family tree.

The Bottom Line

This paper presents a new mathematical "glue" that sticks different versions of a cancer's family tree together. It strips away the confusion to reveal the solid, shared history of the tumor, helping scientists and doctors make more reliable decisions about how to fight cancer. It turns a messy pile of conflicting maps into one clear, trustworthy guide.

Technical Summary

1. Problem Statement

The paper addresses the challenge of comparing and aligning clonal trees (tumor progression trees) derived from cancer genomics data.

• Context: Tumors evolve through the accumulation of somatic mutations, creating subclones. These evolutionary histories are modeled as rooted, unordered, node-labeled trees where nodes represent subclones and labels represent sets of unique mutations acquired at that step.
• The Challenge: Different inference methods (e.g., CONIPHER, PairTree, ScisTree) or different sequencing technologies (bulk vs. single-cell) applied to the same tumor data often yield different tree topologies. Existing methods for comparing trees (like consensus trees or Maximum Agreement Subtrees) either lose topological resolution or fail to account for the specific constraints of clonal trees (e.g., unique mutation labels, unordered siblings).
• Goal: To define and compute an Optimal Multi-Label Tree Alignment (omlta). This involves finding the maximum subset of labeled nodes from two input trees that induce isomorphic subtrees after deleting the minimum number of mutation labels. The cost metric is the Optimal Multi-Label Tree Edit Distance (omltd), defined as the minimum number of label deletions required to make two trees isomorphic, allowing for "free" operations like node expansion (splitting a node with multiple labels into a chain of nodes) and empty node deletion.

2. Methodology

The authors propose a novel algorithmic framework to solve the omlta problem, which is proven to be NP-hard.

A. Formal Definitions

• Input: Two multi-label forests (collections of trees) $F_1$ and $F_2$.
• Operations:
  • Label Deletion: Cost = 1.
  • Node Deletion (of empty nodes): Cost = 0.
  • Node Expansion: Replacing a node with a chain of nodes to distribute its labels. Cost = 0.
• Objective: Transform $F_1$ and $F_2$ into identical forests with minimum total label deletion cost.

B. The Algorithm

The authors present a recursive dynamic programming approach with Fixed-Parameter Tractability (FPT).

1. Recursive Strategy: The algorithm iteratively processes mutation labels. For a label $a$ at the root of a tree in $F_1$, it attempts to match it with a corresponding node in $F_2$.
2. Decision Branching: For each label, the algorithm explores two main branches:
   • Match: Keep the label in both trees. This may require deleting all ancestors of the matching node in the second tree to align the topological position (costing the labels on the path) and potentially expanding nodes.
   • Delete: Remove the label from both trees (costing 2 deletions).
3. Optimization (FPT):
   • A naive recursion would be $O(2^L)$, where $L$ is the total number of labels.
   • The authors improve this to $O(2^{k/2} \cdot L^3 \log L)$, where $k$ is the optimal edit distance (the number of deletions).
   • This is achieved by bounding the recursion depth based on $k$. If the current path of deletions exceeds $k$, the branch is pruned.
   • They utilize a polynomial-time subroutine to check if the distance between two forests is $\le 1$ or $\le 2$, allowing early termination for nearly identical trees.

C. Complexity

• The problem is NP-hard.
• The proposed algorithm is Fixed-Parameter Tractable (FPT) with respect to the edit distance $k$.
• The runtime is strictly better than the state-of-the-art for general unordered tree edit distance ($O(2.62^k)$), offering $O(2^{k/2})$.

3. Key Contributions

1. First Clonal Tree Alignment Tool: Introduction of omlta, the first computational tool specifically designed to align multi-label clonal trees, handling unique mutation labels and unordered siblings.
2. Efficient FPT Algorithm: Development of an algorithm with a running time of $O(2^{k/2} \cdot L^3 \log L)$, making it practical for real-world datasets with hundreds of mutations.
3. Robustness Metric: The ability to quantify the "discordance" between trees inferred by different methods or from different data types, identifying which subclonal structures are robust (conserved across methods) and which are artifacts of inference.
4. Open Source Implementation: Release of the tool at https://github.com/algo-cancer/omlta.

4. Results and Applications

The authors validated omlta on two major datasets:

A. TRACERx NSCLC Cohort (126 Metastatic Tumors)

• Setup: Compared clonal trees inferred by CONIPHER (the standard method used in the TRACERx study) and PairTree (a newer, sampling-based method) on the same bulk whole-exome sequencing (bWES) data.
• Findings:
  • Subtype Differences: Trees for LUAD (Lung Adenocarcinoma) showed significantly higher discordance (higher omltd) than LUSC (Lung Squamous Cell Carcinoma).
  • CCF Correlation: Discordance was negatively correlated with the mean Cancer Cell Fraction (CCF). Tumors with lower CCF (more subclonal heterogeneity) yielded less robust trees across inference methods.
  • Biological Impact: The timing of metastatic branching events (early vs. late) often differed between CONIPHER and PairTree. The omlta alignment provided a "consensus" view, resolving ambiguities and showing that CONIPHER often placed branching events later than PairTree.
  • Gene Robustness: Genes with known roles in cancer (oncogenes/tumor suppressors) were surprisingly less robust in placement than other genes, likely due to complex subclonal selection pressures in LUAD.

B. B2905 Melanoma Preclinical Model

• Setup: Compared trees derived from:
  1. Bulk sequencing (bWES) vs. Bulk transcriptome (bWTS).
  2. Different single-cell sequencing protocols (Smart-seq2 vs. Seq-Well).
  3. Pre- vs. Post-immunotherapy samples.
• Findings:
  • Bulk Data: Trees from bWES and bWTS were highly concordant (low omltd), and omlta could reconcile minor topological differences, effectively increasing resolution.
  • Single-Cell Data: Trees from single-cell data showed much higher discordance (up to 2/3 of shared labels deleted) due to data sparsity and technical noise. However, omlta successfully identified robust lineages preserved across protocols and treatment conditions.
  • Immunotherapy: The alignment of control vs. treated trees revealed specific subclones eliminated by anti-CTLA-4 therapy, highlighting mutations potentially responsible for neoantigens.

5. Significance

• Methodological Advancement: Provides a rigorous mathematical framework for comparing tumor phylogenies, moving beyond simple consensus trees that often collapse critical topological details.
• Clinical Utility: By identifying "robust" subclonal structures, clinicians and researchers can have higher confidence in downstream analyses, such as:
  • Determining the timing of metastasis.
  • Identifying driver mutations that are consistently placed in the tree.
  • Designing combination therapies targeting specific subclones.
• Data Integration: Enables the comparison of trees derived from heterogeneous data sources (e.g., bulk vs. single-cell, different sequencing platforms), facilitating meta-analyses and the validation of new inference algorithms.
• Efficiency: The FPT nature of the algorithm ensures that despite the NP-hard theoretical complexity, the tool is fast enough for practical application on large cancer genomics datasets.