KegAlign: optimizing pairwise alignments with diagonal partitioning

Advances in sequencing and assembly allow the creation of thousands of genome assemblies. However, producing multiple alignments required for their analysis lags behind due to the time-consuming process of pairwise alignment, typically performed by the slow but sensitive tool lastZ. Here, we develop KegAlign, an optimized GPU-enabled pairwise aligner. KegAlign employs a novel diagonal partitioning parallelization strategy and leverages advanced GPU features. It can compute a human/mouse alignment in under 6 h on a GPU-containing node without pre-partitioning, maintaining lastZ-level sensitivity crucial for divergent genomes. KegAlign is available as source code, a Conda package, and a user-friendly Galaxy workflow.