Determining subtree movement distance and consensus between cell trees

Abstract

Tumor mutational heterogeneity can be represented by trees describing the evolutionary history of a tumor. However, noisy sequencing data may create uncertainty in the inferred tree structure, making it important to compare trees and identify the mutations required to transform one into another. We address this problem by defining a tree operation called subtree movement (SBM) and proving that the decision problem associated with the SBM distance is NP-complete. We also establish a close relationship between this distance and the maximum common almost $v$-tree problem (MCAT), which is solvable in polynomial time and provides an upper bound on the SBM distance. For collections of mutation trees, we study two natural consensus formulations: the median problem, which minimizes the sum of distances to the input trees, and the closest problem, which minimizes the maximum distance. We prove that both problems are NP-complete even for only three input trees, considering SBM sequences obtained from MCAT solutions. Finally, we develop algorithms that provide upper bounds for the median and closest problems and evaluate them on synthetic and real datasets. The experiments indicate that the resulting consensus trees summarize the input mutation trees better than any individual tree in the input set.