Robust Discovery of Evolutionary Trajectories in Tumor Multi-Phylogenies

Tumors evolve by accumulating genetic alterations, and the order in which those alterations arise is informative about how the disease progresses. That order is recorded in a tumor phylogeny inferred from sequencing data. A crucial problem is to identify recurrent evolutionary trajectories, patterns of temporal order among alterations that are shared across patients. The state-of-the-art method for this problem is MASTRO, an algorithm that enumerates the trajectories recurring across a cohort and tests their significance. The main limitation of MASTRO is that it assumes one tree per patient. Inference, however, rarely determines a single history: tools return a set of candidate trees, and committing to one of them not only discards the uncertainty but manufactures structure, since an ordering asserted by a single arbitrarily chosen tree is then reported as conserved. This thesis introduces Multi-MASTRO, an extension of MASTRO to sets of trees, carrying each patient’s weighted candidate trees through both discovery and significance testing. In this work we define two natural notions of support for trajectories. Expected support averages a trajectory’s presence over a patient’s set of trees and rewards signals widespread across the cohort; θ-consensus support counts only patients whose trees agree beyond a threshold θ, rewarding signals robust within a patient. We prove that, in general, the resulting families of frequent trajectories are incomparable: neither contains the other. We also introduce a novel null model for this setting, in which a single relabeling is drawn per patient and applied coherently to all of that patient’s candidate trees. This coherent randomization breaks the independence that MASTRO’s Poisson-binomial null assumes, so we compute the exact distribution of each patient’s null score and convolve these distributions across patients; truncating the same distributions at θ yields the consensus test. Both are corrected by Westfall-Young resampling and an empirical false-discovery estimate. We further show that at low support thresholds the dominant cost of mining lies not in the miner but in enforcing trajectory completeness afterwards. This points to a miner operating natively in trajectory space, which we leave as the main direction for future work. On a multi-tree breast-cancer cohort of 1315 patients and 37 809 trees, and on a near single-tree TRACERx cohort, the corrected tests control the family-wise error rate, and the two supports prove complementary on implanted trajectories. Multi-MASTRO removes the sampling variance of a single-tree baseline and suppresses the orderings that one reconstruction invents. Finally, we observe that treating the patient’s candidate trees as independent observations in the significance test, rather than aggregating them into a single per-patient contribution, overstates the evidence.