G-ALN: a GPU-accelerated BWA-aln algorithm for palaeogenomics

Authors

Sharif, B., Hedfors, K., Valk, T. v. d., Heintzman, P. D., Dalen, L.

Abstract

Abstract Summary: The most commonly used method to achieve optimal mapping for short and damaged ancient DNA (aDNA) reads is the BWA-aln algorithm with seeding disabled. However, this CPU-based algorithm is computationally demanding, as the aligner must tolerate mismatches and indels across the entire read. To improve alignment speed, we present G-ALN: a GPU implementation of the BWA-aln and indexing algorithms. G-ALN first searches all reads on GPU cores, with reads that need a long search being shared dynamically between the GPU and any spare CPU cores. Every read is searched using the same algorithm as BWA, so the output is byte-identical, which we confirmed here using woolly mammoth and Neanderthal datasets with aDNA-specific parameters. In our benchmarking, G-ALN indexed a reference genome ~32 times faster than BWA, and read alignment speed increased ~6-fold. G-ALN was developed through AI-assisted coding (Claude Opus 5.5). It processes thousands of reads in parallel on each GPU and aligns more than twice as many aDNA reads per unit of energy. These results show that G-ALN offers a practical route to using GPU resources in established aDNA analysis workflows. Availability and Implementation: G-ALN is implemented in C++ and CUDA and is freely available under the GPLv3 license at https://github.com/bilalbioinfo/galn. It requires an NVIDIA GPU with compute capability 7.0 or higher and CUDA 11.8 or later.

Preprint server: bioRxiv
The authors list and abstract were imported from bioRxiv on 22 Oct 2026.

Stats

1-terrible, 9-excellent. How would you rate this preprint? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.