Exact and Efficient Methods for Identifying Carcinogenic Multi-Hit Gene Combinations
Abstract
Cancer is driven by an estimated two to nine gene mutations, known as multi-hit combinations. Due to the large number of genes, identifying these multi-hit combinations presents a computationally challenging problem, which has previously required supercomputers to enumerate all or most gene combinations. Recent work formulated this classification task as the Multi-Hit Cancer Driver Set Cover Problem (MHCDSCP) and solved it via column generation on a single commodity CPU, where a pricing problem identifies promising gene combinations (arXiv:2602.22551). The main bottleneck is the pricing problem that has to be solved repeatedly. To solve the pricing problem to optimality, we propose a dedicated depth first search method that enumerates all possible gene combinations. Although enumerating gene combinations with depth first search have been performed on supercomputers with around 150,000 CPU cores (arXiv:2603.16721), our depth first search algorithm solves the pricing problem to optimality within seconds on a single CPU by leveraging dual information to prune large parts of the search space. By eliminating this bottleneck, our approach yields the first exact method for the MHCDSCP, which is guaranteed to find a global optimal solution.
Related
- Efficient estimation methods for non-Gaussian regression models in continuous time
- Exact Covariance Structure and Efficient Computation for L-Comoments
- Exact penalty methods with adaptive discretization for nonsmooth semi-infinite optimization
- An efficient and rigorous criterion for the admissible time step of deforming grids in generalized Lagrangian and ALE methods
- Efficient Parameter-Free First-Order Methods for Nonsmooth Composite Minimax Optimization
BibTeX
@misc{willemsen2026exact,
title = {{Exact and Efficient Methods for Identifying Carcinogenic Multi-Hit Gene Combinations}},
author = {Rick S. H. Willemsen and Teresa L. F. Ho and Tenindra Abeywickrama},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09420},
eprint = {2610.09420},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09420},
}
RIS
TY - UNPB
TI - Exact and Efficient Methods for Identifying Carcinogenic Multi-Hit Gene Combinations
AU - Rick S. H. Willemsen
AU - Teresa L. F. Ho
AU - Tenindra Abeywickrama
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09420
UR - https://arxiv.org/abs/2610.09420
AB - Cancer is driven by an estimated two to nine gene mutations, known as multi-hit combinations. Due to the large number of genes, identifying these multi-hit combinations presents a computationally challenging problem, which has previously required supercomputers to enumerate all or most gene combinations. Recent work formulated this classification task as the Multi-Hit Cancer Driver Set Cover Problem (MHCDSCP) and solved it via column generation on a single commodity CPU, where a pricing problem identifies promising gene combinations (arXiv:2602.22551). The main bottleneck is the pricing problem that has to be solved repeatedly. To solve the pricing problem to optimality, we propose a dedicated depth first search method that enumerates all possible gene combinations. Although enumerating gene combinations with depth first search have been performed on supercomputers with around 150,000 CPU cores (arXiv:2603.16721), our depth first search algorithm solves the pricing problem to optimality within seconds on a single CPU by leveraging dual information to prune large parts of the search space. By eliminating this bottleneck, our approach yields the first exact method for the MHCDSCP, which is guaranteed to find a global optimal solution.
ER -