Characterizing the Solution Space of Migration Histories of Metastatic Cancers with MACH2

Understanding the migration history of cancer cells is essential for advancing metastasis research and developing therapies. Existing migration history inference methods often rely on parsimony criteria such as minimizing migrations, comigrations, and seeding locations. Importantly, existing methods either yield a single optimal solution or are probabilistic algorithms without guarantees on optimality nor comprehensiveness of the returned solution space. As such, current methods are unable to capture the full extent of uncertainty inherent to the data. To address these limitations, we introduce MACH2, a method that systematically enumerates all plausible migration histories by exactly solving the P arsimonious M igration H istory with T ree R efinement (PMH-TR). In addition to the migration and comigration criteria, MACH2 employs a novel parsimony criterion that minimizes the number of clones unobserved in their inferred location of origin. MACH2 allows one to specify both the order and the set of criteria to include during optimization, allowing users to adapt the model to specific analysis needs. MACH2 also includes a summary graph to identify high-confidence migrations. Finally, we introduce MACH2-viz, an interactive webtool for visualizing and exploring MACH2 solution spaces. Using simulated tumors with known ground truth, we show that MACH2, especially the version that prioritizes the new unobserved clone criterion, outperforms existing methods. On real data, MACH2 detects extensive uncertainty in non-small cell lung, ovarian, and prostate cancers, and infers migration histories consistent with orthogonal experimental data.