Cancer is often driven by specific combinations of an estimated two to nine gene mutations, known as multi-hit combinations. Identifying these multi-hit combinations of gene mutations that drive cancer is critical for understanding carcinogenesis and designing targeted therapies. We formalize this challenge as the Multi-Hit Cancer Driver Set Cover Problem (MHCDSCP), optimizing the selection of gene combinations to maximize tumor coverage while strictly minimizing normal sample misclassification. While existing approaches rely on exhaustive enumeration and massive parallelization, we introduce fast heuristics based on constraint programming and mixed integer programming formulations. Evaluated on real-world cancer genomics data, our framework matches state-of-the-art supercomputing methods using a single commodity CPU in under a minute. We also propose a price-and-branch heuristic which, by solving the root node to optimality, provides the first provably optimal solutions for over half of the benchmark instances, thereby verifying the near-optimality of our fast heuristics. These findings demonstrate that on real-world problem instances, the MHCDSCP is far less computationally demanding than previously believed, providing an accessible baseline that enables the exploration of previously intractable multi-hit modeling assumptions.
Figures & tables
Figure 1: An example with seven genes and five samples represented as a binary matrix. Two gene combinations with a hit size of two are selected, namely c1 in dark grey and c2 in light grey. Together, they cover tumor samples t1 and t2 (true positives) and normal sample n1 (false positive).
dataset
cancer type
#hits
#genes
#samples
#mutations
\multirow 2*A
BRCA
3, 2–3, 6–7
19,411
1242
837,207
PRAD
6–7, 7
17,274
752
476,115
\multirow 16*B
BLCA-B
4, 6–7, 7
19,408
705
503,615
BRCA-B
3, 2–3, 6–7
20,728
1260
969,254
CESC-B
5, 6–7
20,073
613
430,358
COAD-B
3, 4, 5, 6
20,940
730
737,797
Table 1: Summary of Datasets A and B. For each instance, we report the number of genes, samples, and mutations, as well as the required hit ranges.
cancer type
hit range
solution
training performance
test performance
#comb
obj
solver time (s)
MCC
spec
sens
F1
MCC
spec
sens
F1
\multirow 3*BRCA
2-3
10
677
1200.0
0.984
0.996
0.993
0.996
0.872
0.940
0.952
0.964
3
10
672
1200.0
0.973
0.984
0.991
0.993
0.887
0.940
0.961
0.969
6-7
10
505
1200.0
0.625
0.915
0.779
0.861
0.558
0.855
0.763
0.841
\multirow 2*PRAD
6-7
10
239
1200.0
0.752
0.972
0.782
0.867
0.596
0.952
0.629
0.754
7
10
211
1200.0
0.667
0.952
0.712
0.814
0.525
0.952
0.543
0.687
Table 2: Performance of GR-CP on Dataset A.
cancer type
hit range
solution
training performance
test performance
#comb
obj
solver time (s)
MCC
spec
sens
F1
MCC
spec
sens
F1
\multirow 3*BRCA
2-3
10
678
30.0
0.986
1.000
0.993
0.996
0.878
0.928
0.961
0.967
3
10
677
30.0
0.984
1.000
0.991
0.996
0.864
0.928
0.952
0.962
6-7
10
517
30.0
0.663
0.968
0.773
0.866
0.551
0.880
0.737
0.828
\multirow 2*PRAD
6-7
10
244
17.3
0.775
0.988
0.788
0.877
0.642
0.964
0.667
0.787
7
10
216
22.5
0.692
0.988
0.693
0.814
0.564
0.952
0.590
0.725
Table 3: Performance of GR-MIP on Dataset A.
cancer type
hit range
solution
training performance
test performance
#comb
obj
bound
solver time (s)
MCC
spec
sens
F1
MCC
spec
sens
F1
\multirow 3*BRCA
2-3
10
677
683
51.8
0.984
1.000
0.991
0.996
0.896
0.952
0.961
0.971
3
10
678
683
56.3
0.986
0.996
0.994
0.996
0.843
0.880
0.961
0.958
6-7
10
637
-
300.0
0.891
0.972
0.949
0.969
0.796
0.952
0.895
0.936
\multirow 2*PRAD
6-7
10
280
-
300.0
0.876
0.984
0.899
0.940
0.639
0.916
0.724
0.809
7
10
254
-
300.0
0.783
0.931
0.858
0.897
0.488
0.855
0.629
0.721
Table 4: Performance of Price-and-Branch on Dataset A.
cancer type
hit range
BiGPICC on Dataset A (results reported from [ 28 ] )
GR-MIP on Dataset A
#comb
MCC
spec
sens
F1
#comb
MCC
spec
sens
F1
\multirow 3*BRCA
2-3
5
0.900
0.892
0.987
0.974
10
0.878
0.928
0.961
0.967
3
9
0.900
0.892
0.987
0.974
10
0.864
0.928
0.952
0.962
6-7
34
0.749
0.916
0.882
0.922
10
0.551
0.880
0.737
0.828
\multirow 2*PRAD
6-7
45
0.436
0.831
0.600
0.692
10
0.642
0.964
0.667
0.787
7
62
0.487
0.928
0.533
0.671
10
0.564
0.952
0.590
0.725
Table 5: Comparison of test set performance between BiGPICC (results reported from [ 28 ] ) and GR-MIP on Dataset A.
cancer type
hit range
GR-MIP on Dataset B
Price-and-Branch on Dataset B
obj
gap
total time (s)
#comb
MCC
spec
sens
F1
obj
bound
gap
total time (s)
\multirow 3*BLCA-B
4
280
0.00
18.9
10
0.932
0.952
0.979
0.968
280
280
0.00
42.7
6-7
280
0.00
39.0
10
0.831
0.988
0.840
0.908
279
280
0.36
100.9
7
270
-
39.4
10
0.863
1.000
0.862
0.926
276
-
-
311.7
\multirow 3*BRCA-B
2-3
697
0.00
52.4
9
0.984
0.988
0.996
0.996
697
697
0.00
46.0
3
697
0.00
47.2
7
0.967
0.964
0.996
0.991
697
697
0.00
49.8
Table 6: Test set performance of GR-MIP and Price-and-Branch on Dataset B.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
cancer type
hit range
full MIP
reduced MIP + full MIP
VNS + reduced MIP + full MIP
obj
#iter
MP time (s)
PP time (s)
obj
#iter
MP time (s)
PP time (s)
obj
#iter
MP time (s)
PP time (s)
\multirow 3*BRCA
2-3
665
8
0.0
300.0
669
15
0.0
300.0
677
62
0.1
51.5
3
651
8
0.0
300.0
661
24
0.0
300.0
678
113
0.1
56.1
6-7
590
10
0.0
300.0
615
87
0.1
299.9
637
115
0.2
299.8
\multirow 2*PRAD
6-7
264
17
0.0
300.0
281
177
0.2
299.8
280
212
0.3
299.7
7
235
16
0.0
300.0
257
217
0.2
299.8
254
134
0.1
299.9
Appendix
Table 7: Effect of the pricing problem speedups (corresponding to the three steps in Algorithm 3 ) on Dataset A. We report the number of column generation iterations (#iter). The solver time (in seconds) is split into its two components: solving the restricted master problem (MP) and solving the pricing problem (PP).