Cancer progression models try to recover the order in which mutations accumulate from tumor biopsies, each sampled once at a single time point. The leading family, Mutual Hazard Networks, treats a tumor as a random process that gains mutations one at a time. Each mutation already present speeds up or slows down the arrival of the others; that pairwise modulation is how epistasis, meaning that one mutation's effect depends on which others are present, enters the model. Fitting the model needs, for every patient, a probability computed over all $2^k$ subsets of that patient's $k$ observed mutations. The authors of the mhn package put the practical ceiling at about 25–32 mutations per sample (mhn). Hypermutated tumors exceed that ceiling routinely, so in practice they are dropped or truncated. They are precisely the tumors where the evolutionary history is richest.
The evolutionary-computation literature on epistasis offers a precise way to think about this barrier. There, work on fitness landscapes shows that difficulty is set by the structure of the dependency graph, and in particular by overlapping dependencies, where one variable sits in several interacting groups at once. It is not set by the raw number of variables (Pelikan, NK landscapes). Linkage-learning optimizers turn that observation into an algorithm: they learn the dependency graph and split the problem along its cliques (Andreadis et al.). We propose to apply the same move to the likelihood of a progression model. When we condition on the unknown time at which the biopsy was taken, a tumor's likelihood splits into a product over groups of mutations that do not interact. The cost then scales with the size of the largest interacting group, not with $2^k$.
Core Claim
Our central claim is that the per-sample cost of a Mutual Hazard Network is governed by a sample-specific dependency hypergraph that is easy to compute, not by the mutation count $k$. That hypergraph also explains which samples remain hard. We build it from the patient's observed mutations, and it has one hyperedge per hazard term in the model. For an observed mutation, the hyperedge joins it to the observed mutations that modulate its rate. For an unobserved mutation, the hyperedge joins all observed mutations that modulate its rate.
The second kind of hyperedge is what a naive approach misses. Unobserved events enter the likelihood through the "nothing else happened" exit rates, so an unobserved gene whose hazard is influenced by mutations in two otherwise separate groups couples those groups. This is the overlapping-dependency obstruction of Pelikan in a new setting.
When the hypergraph splits into connected components $g$ of sizes $k_g$, the likelihood factorizes exactly given the sampling time. In the standard MHN setup the sampling time $t$ follows a unit-rate exponential distribution. Writing $x_g$ for the sample's mutations in component $g$ and $P_g(x_g \mid t)$ for the probability that component $g$'s sub-process is in state $x_g$ at time $t$, we get
$$ P(x) \;=\; \int_0^\infty e^{-t} \prod_{g} P_g(x_g \mid t)\, dt . $$
Each factor is a matrix exponential on a $2^{k_g}$-state space, the order-ideal lattice of that group in the language of Beerenwinkel et al.. The one-dimensional integral is evaluated by Gauss–Laguerre quadrature. Total cost is then roughly the number of quadrature nodes times $\sum_g 2^{k_g}$, rather than $2^k$.
When components are still too large, we cut the weakest hyperedges, ranked by a dependency-strength score in the spirit of the fitness-based linkage matrices of Andreadis et al.. We measure the resulting approximation error directly on samples small enough to compute exactly. What is new is not sparsity in MHNs, which $L_1$ penalties already encourage. The contribution is three things the file does not contain: the exact time-conditioned factorization, the identification of unobserved-event hyperedges as the coupling that controls it, and a learned cut rule whose error is checked against exact computation.
Research Program
The first component is analytical. We will prove the factorization for the MHN hazard form, in which the rate of event $i$ is a base rate times the product over present events $j$ of $\exp(\theta_{ji})$. We will extend it to the time-indexed hazards of TimedHN, where a patient-specific pseudo-time replaces the exponential prior. That case is simpler, because conditioning on a known time removes the integral entirely. We will also state the corresponding condition for the two-branch primary/metastasis process of metMHN. There the hypergraph must additionally join any event shared before metastatic seeding across both branches.
The second component is a training procedure that handles the chicken-and-egg problem: the dependency graph is what we are trying to learn. We first fit an ordinary MHN with mhn on samples under the exact-computation ceiling. That model gives a provisional parameter matrix, from which we build each hypermutated sample's hypergraph. We then refit on all samples, using exact factorized likelihoods where components fit a memory budget and cut likelihoods otherwise, and rebuild the hypergraphs every few epochs.
The cut rule works like the gray-box perturbation tests of Andreadis et al.. For each candidate hyperedge we measure how much the log-likelihood of exactly computable samples changes when its parameters are zeroed. We cut the weakest edges first, and the threshold is calibrated on held-out exact samples rather than fixed in advance. That avoids the fixed-threshold weakness noted for linkage learning.
The third component is a diagnostic. For each cohort we will report the distribution of largest-component sizes. Echegoyen et al. show that factorizing models collapse once interactions become dense enough to form a giant cluster. If hypermutated tumors in real cohorts sit beyond that point, we want to show it plainly rather than hide it.
Baselines
The naive reference point is current practice. We fit mhn with state-space restriction (mhn) after either excluding samples above the ceiling, or truncating each such sample to its highest-ranked driver events so that it fits. Both versions use the same gene panel, the same $L_1$ regularization strength chosen by the same cross-validation, and the same GPU budget. Beating it means higher held-out log-likelihood on hypermutated samples. It also means no loss on ordinary samples, and parameter estimates that remain stable when hypermutated samples are added rather than drifting.
The strongest existing exact method is again mhn, but now given the same compute budget as our method and allowed to process every sample it can within that budget. This is the honest head-to-head comparison. The file reports a practical limit of about 25–32 active events per observation for mhn (from mhn). No reported held-out likelihood or edge-recovery number was found on Lacuna for mhn on hypermutated samples. Beating it means processing samples well above 32 mutations with exact or bounded-error likelihoods.
On synthetic data we also compare against TimedHN (TimedHN), using its released code and its random forest and DAG generators. TimedHN is reported to beat CAPRESE, CAPRI, and MHN in F-score and to stay robust under 5% flip noise, but no numeric F-score was found on Lacuna.
Two ablations isolate the key ingredient. The first builds the dependency graph from observed–observed interactions only, ignoring the hyperedges from unobserved events. It shows whether those hyperedges matter. If this cheaper graph gives the same accuracy, our main structural claim is wrong. The second cuts edges at random, matched in number to our cuts, which tests whether the strength-ranked cut rule earns its place.
Why not just…?
Why not just drop or truncate hypermutated samples? This is what is done now, and for many questions it may suffice. It fails in two ways. First, the excluded tumors are a biologically distinct, repair-deficient class whose progression order cannot be studied at all. Second, truncation to top drivers silently removes events whose absence or presence carries information through the exit rates. Our first experiment reports how much held-out likelihood and edge recovery are lost by truncation on synthetic cohorts where the truth is known. If the loss is negligible, the proposal's practical value shrinks to the metastatic and pseudo-time settings, and we will say so.
Why not just estimate the likelihood by sampling random mutation orders (Monte Carlo)? Sampling orders of the $k$ observed events is generic and needs no structure. This is a real threat. With $k!$ possible orders and strongly peaked hazards, however, the variance of the estimate can explode, and the gradients needed for training inherit that noise. The file reports no evaluation of sampling-based MHN training. We will therefore implement an importance sampler that proposes orders from current hazards and compare it at equal wall-clock time. The comparison uses likelihood-error-versus-truth curves on samples with $k \le 20$, where exact values exist, and parameter recovery on synthetic cohorts. If the sampler matches us, the factorization's remaining contribution is exactness where components are small, and we will report that.
Why not just rely on $L_1$ sparsity and larger GPUs? Sparsity alone does not change mhn's computation. It still builds the full $2^k$ restricted space regardless of how many parameters are zero, and doubling memory buys one extra mutation. Sparsity is necessary for our method but not sufficient. The component-size diagnostic will show how often a sparse fitted model still yields a giant component through unobserved-event hyperedges, which neither sparsity nor hardware addresses.
Why not just group genes into pathways first? Gerstung et al. show that pathway-level progression models have lower false-positive rates (FPR ~4–10%), and collapsing genes into pathways shrinks $k$. That is complementary rather than competing. It discards within-pathway order, however, and depends on fixed pathway definitions. We will run our method at both gene and pathway level to show which hypermutated-sample questions survive aggregation.
Proposed Experiments
On synthetic data, we use the mhn generator (mhn) and the TimedHN DAG and forest generators (TimedHN). We plant interaction graphs of controlled sparsity and overlap, and mix in a hypermutated subpopulation with $k$ from 20 to 80.
The decisive first check is exactness. For $k \le 20$, the factorized likelihood must match mhn to numerical precision when components are uncut. The cut likelihood's error must track the summed magnitude of the cut parameters. The second check is recovery: precision, recall, and F-score of interaction edges, together with held-out log-likelihood, as the hypermutated fraction grows, compared against exclusion, truncation, and the Monte Carlo sampler. Sweeping overlap density traces where factorization stops paying, which tests the phase-collapse prediction of Echegoyen et al..
On real data, we use the MSK-IMPACT/AACR GENIE lung adenocarcinoma cohort of 3,662 primary tumors analyzed with mhn, and its 4,852-patient primary/metastasis extension from metMHN. We expand the panel well beyond the original 12–20 genes so that high-burden samples appear. We additionally draw colorectal tumors from the same GENIE release, since repair-deficient tumors are common there. This colorectal cohort is our extension and not a benchmark used in the file.
The decisive real-data checks are three. First, held-out log-likelihood on hypermutated tumors under five-fold cross-validation. Second, whether interactions reported previously, such as the mutual suppression of EGFR and KRAS and the synergy of EGFR and TP53 (mhn), persist once hypermutated tumors are included. Third, the distribution of largest-component sizes. If most hypermutated samples form a single giant component even after strength-ranked cutting, that negative result is itself the finding. It would mean that epistatic overlap, not mutation count, is the true barrier to modeling these tumors.
References
- <tt> mhn </tt> : a Python package for analyzing cancer progression with Mutual Hazard Networks
- Analysis of epistasis correlation on NK landscapes with nearest-neighbor interactions
- Fitness-based Linkage Learning and Maximum-Clique Conditional Linkage Modelling for Gray-box Optimization with RV-GOMEA
- Evolution on distributive lattices
- Timed hazard networks: Incorporating temporal difference for oncogenetic analysis
- Modeling metastatic progression from cross-sectional cancer genomics data
- On the limits of effectiveness in estimation of distribution algorithms
- The Temporal Order of Genetic and Pathway Alterations in Tumorigenesis