Related Experiment Videos
Identifying multi-hit carcinogenic gene combinations: Scaling up a weighted set cover algorithm using compressed
Qais Al Hajri1, Sajal Dash2, Wu-Chun Feng1,2
1Department of Electrical and Computer Engineering, Virginia Tech, Blacksburg, VA, 24060, USA.
Abstract:
Despite decades of research, effective treatments for most cancers remain elusive. One reason is that different instances of cancer result from different combinations of multiple genetic mutations (hits). Therefore, treatments that may be effective in some cases are not effective in others. We previously developed an algorithm for identifying combinations of carcinogenic genes with mutations (multi-hit combinations), which could suggest a likely cause for individual instances of cancer. Most cancers are estimated to require three or more hits. However, the computational complexity of the algorithm scales exponentially with the number of hits, making it impractical for identifying combinations of more than two hits. To identify combinations of greater than two hits, we used a compressed binary matrix representation, and optimized the algorithm for parallel execution on an NVIDIA V100 graphics processing unit (GPU). With these enhancements, the optimized GPU implementation was on average an estimated 12,144 times faster than the original integer matrix based CPU implementation, for the 3-hit algorithm, allowing us to identify 3-hit combinations. The 3-hit combinations identified using a training set were able to differentiate between tumor and normal samples in a separate test set with 90% overall sensitivity and 93% overall specificity. We illustrate how the distribution of mutations in tumor and normal samples in the multi-hit gene combinations can suggest potential driver mutations for further investigation. With experimental validation, these combinations may provide insight into the etiology of cancer and a rational basis for targeted combination therapy.
Insights
Researchers developed a faster algorithm to identify multi-hit gene combinations in cancer, improving diagnosis and paving the way for targeted therapies. This computational advance aids in understanding cancer
Area of Science:
- Computational biology
- Genomics
- Cancer research
Background:
- Effective cancer treatments are limited due to the complex genetic mutations underlying different cancer instances.
- Identifying combinations of mutated genes (multi-hit combinations) is crucial for understanding cancer etiology.
- Previous algorithms were computationally intensive, limiting the analysis to two-hit combinations.
Purpose of the Study:
- To enhance an algorithm for identifying multi-hit gene combinations, specifically three or more genetic mutations.
- To improve computational efficiency for analyzing complex cancer mutation data.
- To enable the identification of potential driver mutations for targeted cancer therapies.
Main Methods:
- Developed a compressed binary matrix representation for genetic data.
- Optimized the algorithm for parallel processing on a graphics processing unit (GPU).
- Compared the GPU implementation's speed against a CPU-based implementation.
Main Results:
- The GPU-optimized algorithm achieved an estimated 12,144-fold speed increase for 3-hit combination identification.
- Identified 3-hit gene combinations differentiated tumor from normal samples with 90% sensitivity and 93% specificity.
- Demonstrated the potential to identify driver mutations from mutation distribution patterns.
Conclusions:
- The enhanced GPU algorithm efficiently identifies complex multi-hit gene combinations in cancer.
- These findings offer insights into cancer origins and support the development of targeted combination therapies.
- Further experimental validation is recommended to confirm driver mutations and therapeutic strategies.