G-ALN: a GPU-accelerated BWA-aln algorithm for palaeogenomics
- 1Centre for Palaeogenetics, Stockholm University, Stockholm, Sweden
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.
Related
- Programmable DNA-Silk hydrogel with temporal mechanical reinforcement for mesenchymal stem cell differentiation and accelerated wound healing
- Muscle stem cell treatment mitigates stress-associated multiorgan dysfunction in D-galactose-induced accelerated aging mice and improves behavior in naturally aged mice
- Copy number variants (CNVs) interfere with human accelerated regions (HARs) in neurodevelopmental disorders: a large-scale cohort study
- Neuron myelination is accelerated by Bruton's tyrosine kinase inhibition via microglial extracellular vesicles.
- TorchGWAS 1.0: GPU-accelerated GWAS at scale.
BibTeX
@misc{sharif2026galn,
title = {{G-ALN: a GPU-accelerated BWA-aln algorithm for palaeogenomics}},
author = {B. Sharif and K. Hedfors and T. v. d. Valk and P. D. Heintzman and L. Dalen},
howpublished = {bioRxiv},
year = {2026},
month = oct,
doi = {10.64898/2026.10.18.759956},
url = {https://www.biorxiv.org/content/10.64898/2026.10.18.759956v1},
note = {CC BY},
}
RIS
TY - UNPB
TI - G-ALN: a GPU-accelerated BWA-aln algorithm for palaeogenomics
AU - B. Sharif
AU - K. Hedfors
AU - T. v. d. Valk
AU - P. D. Heintzman
AU - L. Dalen
PY - 2026
DA - 2026/10/18
PB - bioRxiv
DO - 10.64898/2026.10.18.759956
UR - https://www.biorxiv.org/content/10.64898/2026.10.18.759956v1
AB - 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.
ER -