Read alignment is a time-consuming step in genome sequencing analysis. The most widely used software for read alignment, BWA-MEM, and the recently published faster version BWA-MEM2 are based on the seed-and-extend paradigm for read alignment. The seeding step of read alignment is a major bottleneck contributing ~40% to the overall execution time of BWA-MEM2 when aligning whole human genome reads from the Platinum Genomes dataset. This is because both BWA-MEM and BWA-MEM2 use a compressed index structure called the FMD-Index, which results in high bandwidth requirements, primarily due to its character-by-character processing of reads. For instance, to seed each read (101 DNA base-pairs stored in 37.8 bytes), the FMD-Index solution in BWA-MEM2 requires ~68.5 KB of index data.We propose a novel indexing data structure named Enumerated Radix Tree (ERT) and design a custom seeding accelerator based on it. ERT improves bandwidth efficiency of BWA-MEM2 by 4.5× while guaranteeing 100% identical output to the original software, and still fitting in 64 GB DRAM. Overall, the proposed seeding accelerator implemented on AWS F1 FPGA (f1.4xlarge) improves seeding throughput of BWA-MEM2 by 3.3×. When combined with seed-extension accelerators, we observe a 2.1× improvement in overall read alignment throughput over BWA-MEM2. The software implementation of ERT is integrated into BWA-MEM2 (ert branch: https://github.com/bwa-mem2/bwa-mem2/tree/ert) and is open sourced for the benefit of the research community.

Innovations in genome sequencing techniques are enabling remarkably fast and low cost production of raw genome data. As Moore's law tapers off, bottlenecks in genome sequencing are shifting to computational resources for mapping reads to reference DNA. This paper presents SeedEx, a read-alignment accelerator focused on the seed-extension step. SeedEx is based on the observation that only a small fraction of reads require large edit distance for alignment, hence an area efficient narrow-band seed-extension accelerator can suffice in practice. However, due to the highly error-sensitive nature of genomic workloads, guaranteeing optimality of alignment result is of cardinal importance. Towards this end, we propose a speculation-and-test based framework by using strict but powerful optimality checking mechanisms. We demonstrate SeedEx by an implementation on a cloud FPGA. SeedEx achieves 6.0× iso-area throughput speedup when compared to a banded Smith-Waterman baseline, and achieving 43.9 M seed extentions/s on AWS f1.2xlarge instance. Integration with BWA-MEM2 improves the execution time by 2.3×.