Authors: Zhengyang Bai and Emil Vatai (RIKEN Center for Computational Science (R-CCS)); Ritvik Prabhu and Bernard Moussad (Virginia Tech); Chen Zhuang (Institute of Science Tokyo, RIKEN Center for Computational Science (R-CCS)); Wu-chun Feng (Virginia Tech); and Mohamed Wahib (RIKEN Center for Computational Science (R-CCS))
Abstract: Cancer arises from combinations of somatic mutations (hits), and identifying these combinations is critical for understanding carcinogenesis and enabling targeted therapies. This task can be formulated as a weighted set cover problem, yet exhaustive enumeration leads to exponential search space growth as the number of hits increases, limiting prior enumeration-based work to at most five-hit combinations even on large-scale supercomputers. We propose a novel algorithm that decomposes higher-order combinations through a shortest addition chain and formulates sample coverage computation as matrix multiplication. It employs a robust score-bounded search strategy that eliminates unpromising candidates without evaluation, while guaranteeing that the best-scoring combination is never discarded. Experiments show our method visits less than one-millionth of prior search spaces, identifies four-hit combinations in about five seconds on a single GPU, outperforms thousand-node supercomputers by orders of magnitude, and extends practical reach of enumeration-based cancer screening from five-hit to nine-hit combinations.
Presentation: file