Looking for (Genomic) Needles in a Haystack: Sparsity-Driven Search for Identifying Correlated Genetic Mutations in Cancer

Ritvik Prabhu, Emil Vatai, Bernard Moussad, Emmanuel Jeannot, Ramu Anandakrishnan, Wu-Chun Feng, Mohamed Wahib

TL;DR

The paper introduces Pruned Depth-First Search (P-DFS), a high-performance computing framework that leverages the extreme sparsity of cancer mutation data to drastically prune the astronomical search space of multi-hit genetic mutations. By combining sparsity-aware tree traversal with hierarchical work-stealing on the Fugaku supercomputer, the algorithm eliminates up to 98% of the search space and achieves a 183× speedup, making higher-order cancer mutation analysis computationally feasible for the first time.

What Problem Does This Paper Address?

Cancer rarely develops from a single genetic mutation; instead, it typically results from a combination of multiple genetic alterations accumulating within a cell (often between 2 to 9 "hits"). Identifying these specific co-occurring mutation sets is critical for understanding tumor progression and designing targeted combination therapies.

Estimated number of hits required for oncogenesis across different cancer types.

However, finding these combinations is a classic "needle in a haystack" problem. With roughly 20,000 genes in the human genome, searching for a 4-hit combination requires evaluating $\binom{20,000}{4} \approx 7 \times 10^{15}$ possibilities. Traditional approaches model this as a Weighted Set Cover (WSC) problem—which is NP-complete—requiring exhaustive enumeration of all combinations. On a single CPU, finding 4-hit combinations would take over 500 years, creating a massive computational bottleneck for genomic research.

Methods

The authors propose P-DFS (Pruned Depth-First Search), a framework designed to "prune-then-evaluate" rather than exhaustively search the mutation space.

  1. Sparsity-Aware Preprocessing: The algorithm sorts the gene mutation matrix rows from most sparse to least sparse.
  2. Early-Termination Pruning: P-DFS traverses the combination space using a depth-first search tree. Because tumor mutation data is highly sparse, the intersection of multiple mutated genes frequently yields zero overlapping tumor samples. As soon as a partial combination's intersection evaluates to zero, P-DFS immediately backtracks and prunes the entire remaining subtree.
  3. Loop Flattening for Massive Concurrency: To expose enough parallelism for supercomputers, the first two nested loops of the search space are flattened into a single index ($\lambda$). This expands the number of independent root tasks from 20,000 to roughly $2 \times 10^8$.
  4. Hierarchical Topology-Aware Work Distribution: Implemented via MPI, the framework uses a two-level architecture (node leaders and workers) paired with randomized work-stealing and barrier-free token-based termination to dynamically balance the highly irregular workloads caused by pruning.
Overview of the P-DFS workflow compared to previous exhaustive methods.

Datasets

The framework was evaluated using real-world somatic mutation data from The Cancer Genome Atlas (TCGA). The authors processed multiple distinct cancer cohorts (including bladder urothelial carcinoma [BLCA], breast invasive carcinoma [BRCA], and ovarian serous cystadenocarcinoma [OV]) containing at least 200 samples each. The datasets were split into 75% for training (discovering mutation patterns) and 25% for testing (evaluating generalization).

Key Insights and Ideas

  • Sparsity as an Advantage: Instead of treating data sparsity as a challenge, P-DFS exploits it. Because the median sparsity across TCGA datasets is a staggering 95.61%, the vast majority of deep search branches collapse almost immediately.
  • The "Sparse-First" Optimization: Sorting genes by increasing sparsity does more than accelerate pruning; it fundamentally alters the quality of the solution. At higher hit counts ($h$), dense genes provide redundant information. Sparse genes provide higher marginal information gains, allowing the algorithm to find smaller, more optimal set covers than random or dense-first approaches.
  • Decoupling Communication from Computation: By replicating the small dataset (a few megabytes) across all MPI ranks, the inner-loop operations remain entirely local. Communication is strictly confined to lightweight work-stealing requests and hierarchical collectives, preventing I/O bottlenecks.

Key Results

  • Massive Search Space Reduction: For 4-hit combination searches, P-DFS achieved a 90% to 98% reduction in the number of combinations actually visited.
  • Substantial Speedups: The algorithm demonstrated a 183× speedup over the exhaustive set cover baseline when scaled up to 147,456 ranks (3,072 nodes) on the Fugaku supercomputer.
  • High Biological Discriminative Power: On held-out test data, the discovered multi-hit patterns maintained a high generalization accuracy, yielding a sensitivity of 0.85–0.98 and a specificity of 0.81–0.99.
  • Effective Load Balancing: Enabling the hierarchical work-stealing mechanism collapsed highly irregular worker runtimes into a sharp peak, reducing the standard deviation of worker runtimes by 13× and successfully mitigating straggler effects.

Limitations and Future Work

While P-DFS scales exceptionally well for higher-order hits ($h \ge 3$), the authors note that for low hit counts (like 2-hit searches), the compute workload is so small that fixed communication overheads dominate, causing strong-scaling performance to plateau early.

Additionally, the current framework relies strictly on binary mutation matrices (mutated vs. non-mutated). A natural avenue for future work is extending this sparsity-driven pruning logic to continuous genomic data types, such as gene expression levels, copy number variations, or multi-omic integrations.

Summary updated

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. on the order of 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 framework, 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 (the main contribution of this paper) - 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 weighted set cover 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-hits, and roughly a 183x speedup over the exhaustive set cover approach(which is algorithmically NP-complete) 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.
BibTeX
@inproceedings{prabhu2026looking,
  author = {Ritvik Prabhu and Emil Vatai and Bernard Moussad and Emmanuel Jeannot and Ramu Anandakrishnan and Wu-Chun Feng and Mohamed Wahib},
  title = {{Looking for (Genomic) Needles in a Haystack: Sparsity-Driven Search for Identifying Correlated Genetic Mutations in Cancer}},
  booktitle = {IPDPS},
  year = {2026},
  doi = {10.1109/ipdps65963.2026.00035},
}
Figure