SeAlM: A Query Cache Optimization Technique for Next Generation Sequence Alignment

Genetic data from next-generation sequencing (NGS) technology is being produced at an ever increasing rate - already outpacing the well known Moore's Law. Due to this pace of NGS data generation, new methods are necessary in order to facilitate rapid sequence analysis at the enormous scale required. The need for such methods is further compounded by the dropping financial cost of sequencing, leading to the normalization of large-scale genome studies spanning entire populations. A key process in the genomic data analysis pipeline, and one that is often most time consuming, is read mapping or so-called alignment. This paper introduces Sequence Alignment Memorizer (SeAlM), a technique that reduces the number of redundant alignments to enable population-scale workloads. SeAlM uses a novel method for reordering alignment queries from multiple sources to create batches with increased likelihood of containing redundant queries that can be de-duplicated before alignment, while also ordering those batches to improve the ability to cache queries effectively. We show that our technique can improve the average throughput of alignment for a single human sample by 6.5% and a population of 10 human subjects by 13.6% -18.8% depending on the type of genetic data used.