Koyyalagunta, D.; Morris, Q.

The metastatic spread of a cancer can be reconstructed from DNA sequencing of primary and metastatic tumours, but doing so requires solving a challenging combinatorial optimization problem. This problem often has multiple solutions that cannot be distinguished based on current maximum parsimony principles alone. Current algorithms use ad hoc criteria to select among these solutions, and decide, a priori, what patterns of metastatic spread are more likely, which is itself a key question posed by studies of metastasis seeking to use these tools. Here we introduce Metient, a freely available open-source tool which proposes multiple possible hypotheses of metastatic spread in a cohort of patients and rescores these hypotheses using independent data on genetic distance of metastasizing clones and organotropism. Metient adapts Gumbel-softmax gradient estimators, to quickly map out a Pareto front of migration histories that cover the range of histories that are parsimonious under some criteria. Given a cohort of patients, Metient can calibrate its parsimony criteria, thereby identifying shared patterns of metastatic dissemination in the cohort. Compared with the current state-of-the-art, Metient recovers more migration histories, is more accurate, and is more than 40x faster. Reanalyzing metastasis in 169 patients based on 490 tumors, Metient automatically identifies cancer type-specific trends of metastatic dissemination in melanoma, high-risk neuroblastoma and non-small cell lung cancer. Metient\'s reconstructions usually agree with semi-manual expert analysis, however, in 24 patients, Metient identifies more plausible migration histories than experts, and thus finds that polyclonal seeding of metastases is more common than previously reported.