Back to search

Virginia Tech

Sparsity-Driven Search for Multi-Hit Genetic Mutation Combinations in Cancer

Abstract

dc:description.abstract

Cancer typically arises not from a single genetic mutation (i.e., hit) but from multi-hit combinations that accumulate within cells. However, enumerating multi-hit combinations becomes exponentially more expensive computationally as the number of candidate hit gene combinations grow, i.e. 20,000 choose h, where 20,000 is the number of genes in the human genome and h is the number of hits. To address this challenge, we present an algorithmic technique, called pruned depth-first search (P-DFS), that leverages the high sparsity in tumor mutation data to prune large portions of the search space. Specifically, P-DFS - a pruning technique that exploits sparsity to drastically reduce the otherwise exponential h-hit search space for candidate combinations used by weighted set cover - which is grounded in a depth-first search backtracking technique, prunes infeasible gene subsets early, while a standard greedy weighted set cover (WSC) formulation systematically scores and selects the most discriminative combinations. By intertwining these ideas with optimized bitwise operations and a scalable distributed algorithm on high-performance computing clusters, our algorithm can achieve approximately 90-98% reduction in visited combinations for 4-hit combination and roughly a 183x speedup over the exhaustive set cover approach (whose decision version is NP-complete and whose optimization form is NP-hard) measured on 147,456 ranks. In doing so, our method can feasibly handle four-hit and even higher-order gene hits, achieving both speed and resource efficiency.

Degree

thesis:*
Name thesis:degree_name
Master of Science
Level thesis:degree_level
masters
Discipline thesis:degree_discipline
Computer Science
Department dc:contributor.department
Computer Science and Applications
Grantor dc:publisher
Virginia Tech
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Prabhu, Ritvik
Chair dc:contributor.committeechair
  • Feng, Wu-chun
Committee members dc:contributor.committeemember
  • Wahib, Mohamed
  • Zhang, Liqing

Subjects

dc:subject × 7

Rights

dc:rights
Statement dc:rights
  • In Copyright

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10919/143732

Chain of custody

source
Harvested from
Virginia Tech
Base URL
vtechworks.lib.vt.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Prabhu, Ritvik. Sparsity-Driven Search for Multi-Hit Genetic Mutation Combinations in Cancer. masters thesis, Virginia Tech, 2026. https://hdl.handle.net/10919/143732