Identifying robust subclonal structures through tumor progression tree alignment

Understanding and comparing tumor evolutionary histories is fundamental to cancer genomics, with direct implications for tracking subclonal population dynamics, treatment resistance, and tumor heterogeneity. Clonal trees, widely used to model tumor progression, are rooted, unordered trees in which each node represents a subclone labeled by a set of distinct mutations. Various principled and efficient methods have been developed for inferring clonal trees from either bulk or single-cell sequencing data. However, no existing computational approach offers a method that is both efficient and principled to fully align clonal trees and to compare their subclonal architectures, which limits the robustness of any downstream analysis based on inferred clonal trees. We introduce omlta, the optimal multi-label tree alignment of two clonal trees, which removes the minimum number of mutation labels, so that the remaining trees are isomorphic. Computing omlta is NP-hard. Here, we present a fixed-parameter tractable algorithm to compute the omlta, with a running time of O(L^3 log L 2^k) where L is the number of mutation labels shared between the input trees and k is the minimum possible number of mutation labels that need to be removed for the alignment - which we call omltd, the optimal multi-label tree edit distance. Our approach provides an exponentially better (in k) asymptotic runtime than the state-of-the-art algorithm by Akutsu et al. for computing the classic tree alignment and edit distance, concepts similar to what omlta/omltd optimizes on clonal trees. We applied omlta to 126 multi-sample bulk-sequencing data from the TRACERx study on non-small cell lung cancers by comparing clonal trees inferred by CONIPHER and PairTree. Despite the theoretically exponential runtime, we could compute the tree alignment for each tumor quickly, often within seconds. The omltd between CONIPHER and PairTree clonal trees on the same tumor varies substantially across tumors and the distances are negatively associated with the mean cancer cell fraction among mutations. For the tumors characterized by mutations with low cancer cell fractions, it is thus advisable not to use a single tree, but rather the alignment of multiple alternative trees, so that downstream inferences are informed only by robustly placed mutations. We further evaluated our algorithm on an in-house melanoma sample with clonal trees inferred by PhISCS and ScisTree, highlighting the utility of omlta on trees inferred from single-cell sequencing data. On these datasets, our algorithm completed all analyses in practical wall-clock times and showed that it can identify common evolutionary trajectories among clonal trees representing (i) distinct tumors, (ii) distinct samples from the same tumor, (iii) distinct sequencing data from the same sample. Additional supplementary results demonstrate the robustness of our approach in comparison to alternatives on simulated data.