A Fast and Practical Column Generation Approach for Identifying Carcinogenic Multi-Hit Gene Combinations
This work provides a more efficient computational approach for researchers to identify carcinogenic gene combinations, which is crucial for understanding cancer and developing targeted therapies.
This paper addresses the problem of identifying multi-hit gene combinations that drive cancer by formalizing it as the Multi-Hit Cancer Driver Set Cover Problem (MHCDSCP). The authors developed constraint programming and mixed integer programming formulations that achieve comparable performance to state-of-the-art methods, running on a single CPU in under a minute.
Cancer is often driven by specific combinations of an estimated two to nine gene mutations, known as multi-hit combinations. Identifying these combinations is critical for understanding carcinogenesis and designing targeted therapies. We formalise this challenge as the Multi-Hit Cancer Driver Set Cover Problem (MHCDSCP), a binary classification problem that selects gene combinations to maximise coverage of tumor samples while minimising coverage of normal samples. Existing approaches typically rely on exhaustive search and supercomputing infrastructure. In this paper, we present constraint programming and mixed integer programming formulations of the MHCDSCP. Evaluated on real-world cancer genomics data, our methods achieve performance comparable to state-of-the-art methods while running on a single commodity CPU in under a minute. Furthermore, we introduce a column generation heuristic capable of solving small instances to optimality. These results suggest that solving the MHCDSCP is less computationally intensive than previously believed, thereby opening research directions for exploring modelling assumptions.