Search papers, labs, and topics across Lattice.
This paper introduces Endeavor, a novel parallelization strategy for the Pair Hidden Markov Model (PairHMM) used in DNA variant calling, addressing the significant bottleneck it poses in genomic data processing. By redefining the traditional formulation to utilize row-level fine-grained parallelism, Endeavor achieves unprecedented throughput for both short and long DNA sequences, scaling effectively to 100k basepairs. The results demonstrate that Endeavor outperforms existing methods, achieving up to 2.14x peak throughput compared to GKL and at least 2x speedup over GATK HaplotypeCaller on real-world datasets.
Achieving over 2x speedup in DNA variant calling could revolutionize genomic analysis workflows and accelerate discoveries in complex disease research.
DNA variant calling represents a key operation in bioinformatics pipelines that aims at identifying genetic variants. Given an evidenced explosion in genomic data availability, there is an urgent need for a high-performant, portable and efficient solution for variant calling, which can further improve our understanding of genomic structure and genetic basis for complex diseases. In its most common formulation, the Pair Hidden Markov Model (PairHMM) algorithm for variant calling stands as the main bottleneck in the pipeline, accounting for up to 70% of the execution time in large-scale genomic datasets. The state-of-the-art approaches for accelerating PairHMM in CPUs and GPUs do not scale to long DNA sequences and only explore very limited anti-diagonal data parallelism, which yields poor performance. In this work, Endeavor is proposed as a new parallelization strategy for PairHMM that redefines its traditional formulation to explore row-level fine-grained parallelism without loss in solution accuracy. Based on this, a novel and portable SIMD-based approach is derived for efficient and high-performance processing of short and long sequences in CPUs and GPUs, leveraging novel levels of parallelism and synchronization to achieve high throughput in sequences up to 100k basepairs for the first time. Evaluation on Intel and AMD CPUs shows that Endeavor outperforms GKL up to 2.14x in peak throughput and GATK HaplotypeCaller by at least 2x in real-world datasets, while NVIDIA and AMD GPUs achieve up to 2.05x speedups in genome-scale datasets when compared to state-of-the-art GPU-based methods.
