Algorithmic Improvement and GPU Acceleration of the GenASM Algorithm

03/28/2022

∙

by   Joël Lindegger, et al.

∙

0

∙

share

We improve on GenASM, a recent algorithm for genomic sequence alignment, by significantly reducing its memory footprint and bandwidth requirement. Our algorithmic improvements reduce the memory footprint by 24× and the number of memory accesses by 12×. We efficiently parallelize the algorithm for GPUs, achieving a 4.1× speedup over a CPU implementation of the same algorithm, a 62× speedup over minimap2's CPU-based KSW2 and a 7.2× speedup over the CPU-based Edlib for long reads.