A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets

Barış Ekim, Bonnie Berger, Yaron OrensteinbioRxiv 2020 · DOI

TL;DR

This paper introduces PASHA, a novel randomized parallel algorithm that significantly speeds up the computation of Universal Hitting Sets (UHSs), a crucial data structure for modern genomics. PASHA makes UHS computation practical for larger k-mer lengths (k > 13), which were previously intractable, offering orders-of-magnitude improvements in speed and memory usage.

What Problem Does This Paper Address?

The explosion of sequencing data necessitates efficient methods for processing and indexing it. Universal Hitting Sets (UHSs) have emerged as a promising alternative to traditional minimizer techniques for tasks like read overlap detection and building sparse suffix arrays. A UHS is a set of k-mers that guarantees to contain at least one k-mer from any given sequence of length L. However, existing methods for computing small, near-optimal UHSs are computationally expensive, suffering from long runtimes and high memory demands, especially for the larger k-mer lengths (k > 13) relevant to current sequencing technologies. This limitation hinders their widespread adoption in high-throughput genomics pipelines.

Methods

PASHA tackles the computational bottleneck of UHS generation through two key innovations:

  • Parallelized and Memory-Efficient Hitting Number Calculation: The paper leverages advanced theoretical and architectural techniques to parallelize the calculation of "hitting numbers" (which quantify how many potential sequences a k-mer hits). This involves optimizing dynamic programming approaches and reducing memory footprint by using techniques like storing only the current and previous iterations of path counts and utilizing float data types. They also exploit the relationship between de Bruijn graphs of different orders to further reduce memory.
  • Randomized Parallel Set Cover for k-mer Selection: The core of the UHS generation involves selecting k-mers to cover remaining sequences, which is framed as a Set Cover problem. PASHA adapts a randomized parallel algorithm for Set Cover. Instead of deterministically picking the k-mer that covers the most remaining sequences at each step, PASHA considers a set of candidate k-mers within a specific range of hitting numbers and picks them independently with a constant probability. This introduces randomization and allows for parallel processing, significantly speeding up this phase.

Datasets

The paper evaluates PASHA on various combinations of k-mer length (k) and sequence length (L), ranging from 5 ≤ k ≤ 16 and 20 < L ≤ 200. They also use the entire human reference genome (GRCh38) and 10 random sequences of length 10^6 for density comparisons. No new datasets were introduced; rather, they used existing genomic data and simulated sequences.

Key Insights and Ideas

  • Parallelization is Key for Scalability: The paper demonstrates that parallelizing the hitting number calculation and the k-mer selection process is crucial for overcoming the limitations of serial algorithms, especially for larger k.
  • Randomization as a Speedup Lever: By introducing randomization into the Set Cover phase, PASHA can process multiple k-mers in parallel, achieving significant speedups without drastically compromising the quality (size) of the resulting UHS.
  • UHSs are "Compute Once, Use Many": A critical aspect highlighted is that UHSs are dataset-independent and only need to be computed once. This makes the upfront computational cost of generating a high-quality UHS worthwhile for its subsequent use in various sequence analysis applications.
  • Memory Optimization is as Important as Speed: The paper emphasizes that reducing memory usage is as critical as runtime improvements for practical applicability, especially when dealing with large k-mer spaces.

Key Results

  • Orders of Magnitude Speedup: PASHA achieves orders-of-magnitude improvements in runtime and memory usage compared to existing serial algorithms like DOCKS and its variants.
  • Enabling Larger k: PASHA successfully computes UHSs for k values up to 16, a significant advancement from previous methods limited to k < 13.
  • Near-Optimal Set Sizes: PASHA produces UHSs that are only slightly larger than those generated by serial deterministic algorithms, with provable guarantees that the set size is within a small factor of the optimal. For instance, for k=13, PASHA is significantly faster and produces smaller sets than DOCKSany1000.
  • Comparable Densities: The density of UHSs generated by PASHA is comparable to that of other methods, indicating that the speed and memory improvements do not come at a significant cost to the quality of the generated sets.

Limitations and Future Work

  • Hitting Number Calculation Bottleneck: While PASHA significantly improves the overall process, the calculation of hitting numbers at each iteration remains a bottleneck. The authors pose the question of whether a more efficient method for this calculation exists beyond dynamic programming.
  • Exponential Dependency on k: The inherent exponential dependency of both runtime and memory on k remains a fundamental challenge. While PASHA mitigates this for practical k values, extremely large k might still be prohibitive.
  • Future Work: The authors expect PASHA to be adopted in various genomics applications and suggest that further research into more efficient hitting number calculations could lead to even greater improvements. They also note that for long reads, a simpler approach (hitting all infinite-length sequences) might suffice, but short-read sequencing remains prevalent, making UHS computation for finite lengths highly relevant.

Summary updated

Abstract

Abstract As the volume of next generation sequencing data increases, an urgent need for algorithms to efficiently process the data arises. Universal hitting sets (UHS) were recently introduced as an alternative to the central idea of minimizers in sequence analysis with the hopes that they could more efficiently address common tasks such as computing hash functions for read overlap, sparse suffix arrays, and Bloom filters. A UHS is a set of k -mers that hit every sequence of length L , and can thus serve as indices to L -long sequences. Unfortunately, methods for computing small UHSs are not yet practical for real-world sequencing instances due to their serial and deterministic nature, which leads to long runtimes and high memory demands when handling typical values of k (e.g. k &gt; 13). To address this bottleneck, we present two algorithmic innovations to significantly decrease runtime while keeping memory usage low: (i) we leverage advanced theoretical and architectural techniques to parallelize and decrease memory usage in calculating k -mer hitting numbers; and (ii) we build upon techniques from randomized Set Cover to select universal k -mers much faster. We implemented these innovations in PASHA, the first randomized parallel algorithm for generating near-optimal UHSs, which newly handles k &gt; 13. We demonstrate empirically that PASHA produces sets only slightly larger than those of serial deterministic algorithms; moreover, the set size is provably guaranteed to be within a small factor of the optimal size. PASHA’s runtime and memory-usage improvements are orders of magnitude faster than the current best algorithms. We expect our newly-practical construction of UHSs to be adopted in many high-throughput sequence analysis pipelines.
BibTeX
@misc{ekim2020randomized,
  author = {Barış Ekim and Bonnie Berger and Yaron Orenstein},
  title = {{A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets}},
  year = {2020},
  doi = {10.1101/2020.01.17.910513},
  howpublished = {bioRxiv},
}
Figure