Exact and Efficient Methods for Identifying Carcinogenic Multi-Hit Gene Combinations
In the authors' words
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.
In plain words AI summary
Cancer develops from two to nine gene mutations working together, called multi-hit combinations. Finding these combinations is computationally hard and previously needed supercomputers. The authors created a depth-first search method that solves the key pricing problem to optimality. Their algorithm runs in seconds on a single CPU by using dual information to prune the search space. This yields the first exact method guaranteed to find a global optimal solution.
Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source.
Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 13 pages