Determining distances and consensus between mutation trees

Luís Cunha, Jack Kuipers, Thiago LopesarXiv 2025 · DOI · arXiv

Introduction: The Challenge of Tumor Heterogeneity

Cancer is fundamentally an evolutionary process. As a tumor progresses, cells accumulate distinct mutations, creating a branching lineage that can be modeled as a mutation tree. Understanding these trees is essential for clinical practice, as they help predict tumor evolution and potential resistance to treatment.

However, modern single-cell sequencing technology is inherently noisy, frequently introducing false positives, false negatives, or missing data. Consequently, instead of a single definitive evolutionary history, researchers often generate a "forest" of candidate trees—a set of co-optimal or likely structures.

Figure 4: Examples of candidate mutation trees (a, b, c) derived from noisy sequencing data, illustrating the topological variation researchers must reconcile.

Until now, the field has lacked a standard, efficient methodology to quantify the distance between these trees or to identify a "consensus" tree that best represents the entire noisy collection.

Methodology: Quantifying Tree Distances and Finding Consensus

This paper introduces a formal framework for measuring tree distance based on the minimum number of operations—specifically moving a subtree up or down one level—required to transform one tree into another.

Distance Calculations

For simple trees with a height $\le 2$, the authors demonstrate that the problem is equivalent to the "swap distance" between permutations, solvable in linear time. For more complex, general trees, they introduce the Maximum Common Almost v-tree (MCAT) problem. This approach identifies the largest shared substructures between two trees to compute their distance with an efficient $O(n^3)$ time complexity.

Figure 1: Visualizing the relationship between tree structures (a) and mutation matrices (b, c). The red symbols in matrix (b) represent noisy or missing data that the consensus framework aims to resolve in (c).

Consensus Algorithms

To synthesize a representative tree from a set of $k$ candidates, the authors propose two primary heuristics:

  1. Generalized MCAT: This algorithm contracts common subtrees across the entire set to build a consensus structure.
  2. Phylogenetic Approach: An iterative method that identifies the closest pair of trees in a set and merges them recursively until a single tree remains.

Results: Computational Efficiency and Biological Accuracy

Complexity and Performance

The authors provide a rigorous proof that finding the mathematically optimal Median tree (minimizing the sum of distances) or Closest tree (minimizing the maximum distance) is NP-complete, even for as few as three input trees. This finding justifies the use of efficient heuristics.

In practical evaluations, the MCAT-based algorithm proved significantly faster than iterative phylogenetic methods. For instance, on the "Navin" dataset, MCAT reached a solution in approximately 31 seconds, whereas the phylogenetic approach required over an hour (3,754 seconds).

Biological Integrity

Beyond speed, the MCAT-based approach excels at preserving the internal branching structure of input trees. In experiments on real-world datasets (such as Hou78), the algorithms produced consensus trees that were more "central" (exhibiting lower median distances to the input set) than any individual tree found in the original noisy sequencing output. This ensures that the resulting summary is both mathematically representative and biologically plausible.

Conclusion and Future Directions

The proposed $O(n^3)$ distance calculation allows this framework to scale to trees with dozens of nodes, matching the requirements of typical clinical gene panels. While the current algorithms provide high-quality approximations for NP-complete problems, future work may involve Hyperdimensional Computing (HDC). By mapping complex tree structures into high-dimensional vector spaces, researchers hope to achieve even faster pattern matching and more robust tree synthesis for massive genomic datasets.

Summary updated

BibTeX
@misc{cunha2025determining,
  author = {Luís Cunha and Jack Kuipers and Thiago Lopes},
  title = {{Determining distances and consensus between mutation trees}},
  year = {2025},
  eprint = {2501.07529},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.07529},
}
Figure