Rate-Corrected Driver Pathway Search as Difference-of-Submodular Optimization

Cancer genomes carry thousands of mutations. Most are "passengers" that do nothing, and a few are "drivers" that help the tumor grow. A classic way to find drivers that are individually rare is to look for groups of genes that together cover many patients but are rarely mutated in the same patient. This pattern, called mutual exclusivity, arises because one hit to a pathway is enough. Current search tools score gene sets with a count that assumes every gene picks up random mutations at the same rate. That assumption fails badly for very long genes, which collect random hits simply because they are large. Once the score is corrected by subtracting the coverage each set would get by chance under gene-specific rates, the corrected score becomes a difference of two "diminishing-returns" (submodular) set functions. Greedy search has no guarantees on functions of this kind. It is exactly the class for which continuous difference-of-convex algorithms were recently shown to reach better solutions.

We propose to build that rate-corrected objective, optimize it over all genes with continuous difference-of-convex programming, and test the result. The test asks whether this recovers long-tail driver pathways that greedy, sampling, and exact integer programming miss or cannot reach at whole-exome scale, while rejecting the large-gene artifacts that fool the uncorrected score. A side benefit is that the chance-coverage term penalizes set size naturally. The pathway size no longer has to be fixed in advance, and that fixed size is a stated limitation of current formulations.

Core Claim

The obvious bridge between these literatures is to take the Dendrix weight of De novo discovery of mutated driver pathways in cancer and hand it to a continuous optimizer. We think that bridge is a mistake, and saying why sets up the actual proposal.

Write $A \in \{0,1\}^{m \times n}$ for the patient-by-gene mutation matrix, $\Gamma(M)$ for the patients with at least one mutation in gene set $M$, and $C(M) = |\Gamma(M)|$ for coverage. The Dendrix weight is coverage minus overlap, which works out to $2C(M) - \sum_{g \in M} |\Gamma(g)|$. That is a submodular function plus a modular (additive) one, so it is simply submodular. Maximizing a submodular function under a size limit is well served by greedy methods. At the cohort sizes studied so far (hundreds of genes, under 200 patients), it is also easily solved exactly as an integer program. Applying difference-of-convex machinery to it would be overkill, and a reviewer would be right to say so.

The structure changes once the score accounts for gene-specific passenger rates. Let $p_{ig}$ be the probability that passenger processes alone mutate gene $g$ in patient $i$. This probability would be estimated from coding length and the patient's overall mutation burden, which are the confounders documented by Driver gene classification reveals a substantial overrepresentation of tumor suppressors among very large chromatin-regulating proteins and Comprehensive identification of mutational cancer driver genes across 12 tumor types. We score a set by how much its observed coverage exceeds chance coverage, minus an overlap penalty with weight $\lambda \ge 0$:

$$F(M) = (1+\lambda)\,C(M) \;-\; \lambda \sum_{g\in M}|\Gamma(g)| \;-\; \sum_{i=1}^{m}\Big(1-\prod_{g\in M}(1-p_{ig})\Big).$$

The last term is the expected coverage under independent gene-specific passenger rates. It is a probabilistic coverage function, and so it is itself submodular. Maximizing $F$ therefore means minimizing $G(M) - H(M)$. Here $G$ is the chance coverage plus the modular term, and $H = (1+\lambda)C$. Both are submodular, so this is a genuine difference-of-submodular problem. This is the setting of Difference of submodular minimization via DC programming. That paper extends both set functions to convex functions over the unit cube using the Lovász extension, runs the DC algorithm with rounding at each step, and proves strong local minimality in the discrete problem. It also reports that discrete difference-of-submodular heuristics stall at worse objective values.

The chance-coverage term grows with every added gene, so $F$ stops rewarding sets once a new gene adds only coverage that chance would explain. This lets us optimize without a size constraint, removing the fixed-$k$ requirement noted in Finding Driver Pathways in Cancer: Models and Algorithms. It also turns the uniform-rate limitation noted there and in Modeling Mutual Exclusivity of Cancer Mutations from a caveat into part of the objective.

Research Program

The first component is the null model. We fit $p_{ig}$ as a logistic function of the log of coding length, gene-level covariates such as expression and chromatin compactness, and per-patient mutation burden, using only synonymous or other presumed-neutral mutations. That keeps the null fit from absorbing driver signal. The result is a dense matrix, but it is cheap to store in factored form, and the chance-coverage term can be evaluated from it patient by patient.

The second component is the optimizer. Each DC iteration takes a subgradient of the Lovász extension of $H$. Coverage makes this cheap: it comes from one sort of the current continuous point and a sweep over the sparse mutation matrix. The step then minimizes the Lovász extension of $G$ minus that linear term. This is a submodular minimization problem, which is solvable in polynomial time but slow in practice over roughly 20,000 genes. We will solve it approximately with warm-started Frank-Wolfe and round at every iteration, following the regularized variants (DCAR, CDCAR) of El Halabi et al. To find multiple pathways, we peel them off one at a time: we remove the found genes' contribution from $H$ and re-solve. This extends their method from a feature-selection problem with 118 binary features to a sparse matrix with tens of thousands of columns. Showing that the per-iteration cost stays practical at that size is itself one of the questions this work must answer.

The third component is significance testing. We test each returned set by re-running the full optimizer on matrices resampled from the fitted null, so the test accounts for the search itself. For the top sets, we also run the error-aware likelihood test of Modeling Mutual Exclusivity of Cancer Mutations, which models false positive and false negative rates. That keeps its sequencing-noise protection, which our score lacks, and restricts it to the candidate lists it was designed for.

Baselines

The naive reference point is the uncorrected Dendrix weight optimized by GreedyWeight with a fixed $k$ (Finding Driver Pathways in Cancer: Models and Algorithms). That paper reports that GreedyWeight converged to the same maximum-weight set in 58% of runs on 91 glioblastoma patients. We also include plain recurrence ranking, which is known to fail when drivers mutate no more often than passengers. Beating these means rejecting large-gene artifacts that they select, while matching their recovery of known pathways such as the CDKN2B/RB1/CDK4 and EGFR/KRAS/STK11 sets from De novo discovery of mutated driver pathways in cancer.

The strongest competitors on the optimization question all run on our corrected objective $F$, with identical inputs and wall-clock budgets. They are randomized multi-start greedy, the Dendrix MCMC sampler, and an exact mixed-integer program solved with Gurobi. The mixed-integer program linearizes chance coverage per patient: coverage probability is $1 - \exp(\sum_g x_g \log(1-p_{ig}))$, a function of one linear sum, so it can be approximated piecewise-linearly to any chosen accuracy. We also include a Bernoulli-relaxation optimizer in the style of Differentiable Integer Linear Programming, which reports 97.1% feasibility on independent-set instances and a 13.2x training speedup over solver-supervised pipelines. It will get the same gradient-step budget as our method. Beating this group means reaching a higher $F$ at equal time on large instances, and a small certified gap to the exact optimum where the exact program finishes.

For gene-level ranking, the strongest existing method in the file is DriverRWH (DriverRWH: discovering cancer driver genes by random walk on a gene mutation hypergraph). It reports recovering about 50% of known drivers in the top 30 candidates for more than half of 31 TCGA cancer types. We will run it on the same 31-type cohort, using the same known-driver reference, and count beating it as higher top-30 recall in a majority of cancer types without using a protein interaction network. SBM-GNN reports an AUC of 0.8948 on STRING-based PCAWG labels (Discovering cancer driver genes and pathways using stochastic block model graph neural networks), but that result is on a different data setup. We cite it for context rather than as a head-to-head target.

Two ablations isolate the two ingredients. Running the DC optimizer on the uncorrected objective tests whether the correction or the optimizer matters. Running greedy and MCMC on the corrected objective, as above, tests the reverse.

Why not just…?

Why not just run greedy or MCMC on the corrected score? This is the most serious threat. Greedy's guarantees are lost on difference-of-submodular objectives, and El Halabi et al. show discrete heuristics for this class stalling at worse objective values. That evidence, however, comes from speech and Mushroom feature selection (no reported number found on Lacuna for the Mushroom objective values), not from mutation matrices. If multi-start greedy matches the DC method in $F$ at equal time on the pan-cancer cohorts, then the contribution shrinks to the corrected objective alone. The optimizer ablation is designed to report that outcome plainly.

Why not just solve it exactly with an integer program? On the small glioblastoma and lung matrices it probably can be solved exactly, and there we use it as the ground truth for optimality gaps rather than as a competitor. The open question is the 3,205-tumor and 9,183-tumor cohorts at full exome width. There, the piecewise linearization multiplies constraints per patient, and we will report where exact solving stops finishing within budget.

Why not just pre-filter to frequently mutated genes and run the original tools? Pre-filtering by frequency discards exactly the long-tail genes this work targets. It also keeps long genes that are frequent only because of their size. We will measure how many planted rare pathway members survive standard frequency filters in simulation.

Why not just use a deep model such as GIT? From Genome to Phenome reaches an F1 of 62.7% against 56.0% for Lasso on expression prediction. By its own account, though, it learns associations and does not enforce exclusivity. It answers a different question and needs matched expression data. We treat its attention-ranked genes as an extra ranking to compare against, not a replacement.

Proposed Experiments

We start with simulation, where the truth is known. We plant pathways of varying size in matrices whose passenger rates scale with real gene lengths, including the regime from Vandin et al. where drivers mutate at passenger frequency. We then measure pathway recovery (Jaccard similarity to the planted sets), the rate of false inclusion of long genes, how well the method infers pathway size without being given $k$, and objective value against exact optima.

On real data, we use TCGA glioblastoma and lung adenocarcinoma as sanity checks against published pathways. The 12-type cohort of Comprehensive identification of mutational cancer driver genes across 12 tumor types and the 31-type cohort serve as scale tests. There, we score enrichment of returned genes in Tamborero et al.'s 291 drivers and in the 165-gene high-confidence set of Waks et al. Genes from the Waks set are held out from any null-model tuning.

Two checks are decisive. The corrected objective must remove long, non-driver genes from top sets without losing known drivers; if it does not, the null model is wrong. And, at equal time on the large cohorts, the DC optimizer must reach a higher corrected score than multi-start greedy and MCMC; if it does not, the continuous machinery is unnecessary and we will say so.