{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T12:55:30Z","timestamp":1782132930378,"version":"3.54.5"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,6,21]],"date-time":"2026-06-21T00:00:00Z","timestamp":1782000000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T00:00:00Z","timestamp":1782086400000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Johannes Gutenberg-Universit\u00e4t Mainz"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>The continually increasing volume of sequence data results in a growing demand for fast implementations of core algorithms. Computation of pairwise alignments based on dynamic programming is an important part in many bioinformatics pipelines and a major contributor to overall runtime due to the associated quadratic time complexity. This motivates the need for a library of efficient implementations on modern GPUs for a variety of alignment algorithms for different types of sequence data including DNA, RNA, and proteins.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Accelign is a library of accelerated pairwise sequence alignment algorithms for CUDA-enabled GPUs. Its parallelization strategy is based on a common wavefront design that can be adapted to support a variety of dynamic programming algorithms: local, global, and semi-global alignment of genomic and protein sequences with a variety of commonly used scoring schemes supporting one-to-one, one-to-many or all-to-all pairwise sequence alignments. This leads to a peak performance between 16.1 TCUPS and 9.1 TCUPS for computing optimal global alignment scores with linear gaps and affine gap penalties on a single RTX PRO 6000 Blackwell GPU, respectively. In addition, our library demonstrates significant speedups in several real-world case studies over prior CPU-based (SeqAn, Parasail, BSalign, EdLib, KSW2, WFA2, A*PA2) and GPU-based libraries (ADEPT, GASAL2), and can even outperform highly customized algorithms (WFA-GPU, CUDASW++4.0). Furthermore, the performance of our approach scales linearly with the number of employed GPUs, which makes it feasible to exploit multi-GPU nodes for increased processing speeds.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion<\/jats:title>\n                    <jats:p>\n                      Accelign provides significant speedups for commonly used pairwise alignment algorithms compared to prior implementations. It is freely available at\n                      <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/github.com\/fkallen\/Accelign\" ext-link-type=\"uri\">https:\/\/github.com\/fkallen\/Accelign<\/jats:ext-link>\n                      .\n                    <\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-026-06521-0","type":"journal-article","created":{"date-parts":[[2026,6,21]],"date-time":"2026-06-21T08:46:28Z","timestamp":1782031588000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Accelign: a GPU-based library for accelerating pairwise sequence alignment"],"prefix":"10.1186","volume":"27","author":[{"given":"Felix","family":"Kallenborn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fawaz","family":"Dabbaghie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Steinegger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bertil","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,21]]},"reference":[{"key":"6521_CR1","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.jbiotec.2017.07.017","volume":"261","author":"K Reinert","year":"2017","unstructured":"Reinert K, Dadi TH, Ehrhardt M, Hauswedell H, Mehringer S, Rahn R, et al. The seqan c++ template library for efficient sequence analysis: a resource for programmers. J Biotechnol. 2017;261:157\u201368.","journal-title":"J Biotechnol"},{"issue":"20","key":"6521_CR2","doi-asserted-by":"publisher","first-page":"3437","DOI":"10.1093\/bioinformatics\/bty380","volume":"34","author":"R Rahn","year":"2018","unstructured":"Rahn R, Budach S, Costanza P, Ehrhardt M, Hancox J, Reinert K. Generic accelerated sequence alignment in seqan using vectorization and multi-threading. Bioinformatics. 2018;34(20):3437\u201345.","journal-title":"Bioinformatics"},{"key":"6521_CR3","doi-asserted-by":"crossref","unstructured":"Misra S, Pan TC, Mahadik K, Powley G, Vaidya PN, Vasimuddin M, Aluru S. Performance extraction and suitability analysis of multi-and many-core architectures for next generation sequencing secondary analysis. In: Proc. of the 27th International Conference on Parallel Architectures and Compilation Techniques, p. 3 (2018). ACM","DOI":"10.1145\/3243176.3243197"},{"issue":"1","key":"6521_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-016-0930-z","volume":"17","author":"J Daily","year":"2016","unstructured":"Daily J. Parasail: Simd c library for global, semi-global, and local pairwise sequence alignments. BMC Bioinform. 2016;17(1):1.","journal-title":"BMC Bioinform"},{"key":"6521_CR5","doi-asserted-by":"publisher","first-page":"82138","DOI":"10.1371\/journal.pone.0082138","volume":"8","author":"M Zhao","year":"2013","unstructured":"Zhao M, Lee WP, Garrison EP, Marth GT. Ssw library: an simd smith-waterman c\/c++ library for use in genomic applications. PLoS ONE. 2013;8:82138.","journal-title":"PLoS ONE"},{"key":"6521_CR6","doi-asserted-by":"crossref","unstructured":"Liu Y, Schmidt B. Swaphi: Smith-waterman protein database search on xeon phi coprocessors. In: IEEE 25th International Conference on Application-Specific Systems, Architectures and Processors. IEEE; 2014. p. 184\u20135.","DOI":"10.1109\/ASAP.2014.6868657"},{"key":"6521_CR7","doi-asserted-by":"crossref","unstructured":"Shao H, Ruan J. Bsalign: a library for nucleotide sequence alignment. Genomics, Proteomics & Bioinformatics, 025 (2024)","DOI":"10.1101\/2024.01.15.575791"},{"issue":"9","key":"6521_CR8","doi-asserted-by":"publisher","first-page":"1394","DOI":"10.1093\/bioinformatics\/btw753","volume":"33","author":"M \u0160o\u0161i\u00e7","year":"2017","unstructured":"\u0160o\u0161i\u00e7 M, \u0160iki\u00e7 M. Edlib: a c\/c++ library for fast, exact sequence alignment using edit distance. Bioinformatics. 2017;33(9):1394\u20135. https:\/\/doi.org\/10.1093\/bioinformatics\/btw753.","journal-title":"Bioinformatics"},{"issue":"18","key":"6521_CR9","doi-asserted-by":"publisher","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","volume":"34","author":"H Li","year":"2018","unstructured":"Li H. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics. 2018;34(18):3094\u2013100. https:\/\/doi.org\/10.1093\/bioinformatics\/bty191.","journal-title":"Bioinformatics"},{"issue":"Suppl 1","key":"6521_CR10","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1186\/s12859-018-2014-8","volume":"19","author":"H Suzuki","year":"2018","unstructured":"Suzuki H, Kasahara M. Introducing difference recurrence relations for faster semi-global alignment of long sequences. BMC Bioinform. 2018;19(Suppl 1):45.","journal-title":"BMC Bioinform"},{"key":"6521_CR11","doi-asserted-by":"crossref","unstructured":"Koerkamp RG. A* pa2: Up to 19$$\\times $$ faster exact global alignment. Leibniz International Proceedings in Informatics (LIPIcs). 2024;312:1\u201317.","DOI":"10.1101\/2024.03.24.586481"},{"key":"6521_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.future.2023.07.008","volume":"149","author":"A Haghi","year":"2023","unstructured":"Haghi A, Marco-Sola S, Alvarez L, Diamantopoulos D, Hagleitner C, Moreto M. Wfa-fpga: An efficient accelerator of the wavefront algorithm for short and long read genomics alignment. Futur Gener Comput Syst. 2023;149:39\u201358.","journal-title":"Futur Gener Comput Syst"},{"key":"6521_CR13","doi-asserted-by":"crossref","unstructured":"Costanzo M, Rucci E, Garc\u00eda-S\u00e1nchez C, Naiouf M, Prieto-Mat\u00edas M. Analyzing the performance portability of sycl across cpus, gpus, and hybrid systems with sw sequence alignment. Futur Gener Comput Syst. 2025;107838.","DOI":"10.1016\/j.future.2025.107838"},{"key":"6521_CR14","doi-asserted-by":"crossref","unstructured":"Sandes EFO, Melo AC. Cudalign: using gpu to accelerate the comparison of megabase genomic sequences. In: Proceedings PPoPP 2010, vol. 45. ACM; 2010. p. 137\u201346.","DOI":"10.1145\/1837853.1693473"},{"issue":"1","key":"6521_CR15","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1186\/1471-2105-14-117","volume":"14","author":"Y Liu","year":"2013","unstructured":"Liu Y, Wirawan A, Schmidt B. Cudasw++ 3.0: accelerating smith-waterman protein database search by coupling cpu and gpu simd instructions. BMC Bioinform. 2013;14(1):117.","journal-title":"BMC Bioinform"},{"issue":"19","key":"6521_CR16","doi-asserted-by":"publisher","first-page":"2494","DOI":"10.1093\/bioinformatics\/btt410","volume":"29","author":"M Korpar","year":"2013","unstructured":"Korpar M, \u0160iki\u0107 M. Sw#-gpu-enabled exact alignments on genome scale. Bioinformatics. 2013;29(19):2494\u20135.","journal-title":"Bioinformatics"},{"issue":"10","key":"6521_CR17","first-page":"2838","volume":"27","author":"EF Oliveira Sandes","year":"2016","unstructured":"Oliveira Sandes EF, Miranda G, Martorell X, Ayguade E, Teodoro G, Melo ACM. Cudalign 4.0: incremental speculative traceback for exact chromosome-wide alignment in gpu clusters. IEEE TPDS. 2016;27(10):2838\u201350.","journal-title":"IEEE TPDS"},{"issue":"1","key":"6521_CR18","first-page":"1","volume":"20","author":"N Ahmed","year":"2019","unstructured":"Ahmed N, L\u00e9vy J, Ren S, Mushtaq H, Bertels K, Al-Ars Z. Gasal2: a gpu accelerated sequence alignment library for high-throughput ngs data. BMC Bioinform. 2019;20(1):1\u201320.","journal-title":"BMC Bioinform"},{"issue":"1","key":"6521_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-020-03720-1","volume":"21","author":"MG Awan","year":"2020","unstructured":"Awan MG, Deslippe J, Buluc A, Selvitopi O, Hofmeyr S, Oliker L, et al. Adept: a domain independent sequence alignment strategy for gpu architectures. BMC Bioinform. 2020;21(1):1\u201329.","journal-title":"BMC Bioinform"},{"key":"6521_CR20","unstructured":"Pantaleoni J, Subtil N. NVBIO. https:\/\/nvlabs.github.io\/nvbio (2015)"},{"issue":"1","key":"6521_CR21","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1186\/s12859-024-05965-6","volume":"25","author":"B Schmidt","year":"2024","unstructured":"Schmidt B, Kallenborn F, Chacon A, Hundt C. Cudasw++ 4.0: ultra-fast gpu-based smith-waterman protein sequence database search. BMC Bioinform. 2024;25(1):342.","journal-title":"BMC Bioinform"},{"key":"6521_CR22","doi-asserted-by":"crossref","unstructured":"Kallenborn F, Chacon A, Hundt C, Sirelkhatim H, Didi K, Cha S, et al. Gpu-accelerated homology search with mmseqs2. Nat Methods. 2025;1\u20134.","DOI":"10.1101\/2024.11.13.623350"},{"key":"6521_CR23","doi-asserted-by":"crossref","unstructured":"M\u00fcller A, Schmidt B, Membarth R, Lei\u00dfa R, Hack S. Anyseq\/gpu: a novel approach for faster sequence alignment on gpus. In: Proceedings of the 36th ACM International Conference on Supercomputing. 2022. p. 1\u201311.","DOI":"10.1145\/3524059.3532376"},{"key":"6521_CR24","doi-asserted-by":"crossref","unstructured":"Sousa WP, Soares FM, Brum RC, Figueiredo M, Melo AC, Castro MCS, Bentes C. Biological sequence comparison on cloud-based gpu environment. In: High Performance Computing in Clouds: Moving HPC Applications to a Scalable and Cost-Effective Environment, pp. 239\u2013263. Springer, ??? (2023)","DOI":"10.1007\/978-3-031-29769-4_12"},{"key":"6521_CR25","doi-asserted-by":"crossref","unstructured":"Park S, Hong J, Song J, Kim H, Kim Y, Lee J. Agatha: Fast and efficient gpu acceleration of guided sequence alignment for long read mapping. In: Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, pp. 431\u2013444 (2024)","DOI":"10.1145\/3627535.3638474"},{"key":"6521_CR26","doi-asserted-by":"crossref","unstructured":"Oliver T, Schmidt B, Maskell D. Hyper customized processors for bio-sequence database scanning on fpgas. In: Proceedings of the 2005 ACM\/SIGDA FPGA. ACM; 2005. p. 229\u201337.","DOI":"10.1145\/1046192.1046222"},{"key":"6521_CR27","doi-asserted-by":"crossref","unstructured":"Li ITS, Shum W, Truong K. 160-fold acceleration of the smith-waterman algorithm using a field programmable gate array (fpga). BMC Bioinformatics. 2007;8:","DOI":"10.1186\/1471-2105-8-185"},{"issue":"3","key":"6521_CR28","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1177\/1094342016654215","volume":"32","author":"E Rucci","year":"2018","unstructured":"Rucci E, Garcia C, Botella G, De Giusti AE, Naiouf M, Prieto-Matias M. Oswald: Opencl smith\u2013waterman on altera\u2019s fpga for large protein databases. Int J High Perform Comput Appl. 2018;32(3):337\u201350.","journal-title":"Int J High Perform Comput Appl"},{"issue":"5","key":"6521_CR29","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1186\/s12918-018-0614-6","volume":"12","author":"E Rucci","year":"2018","unstructured":"Rucci E, Garcia C, Botella G, De Giusti A, Naiouf M, Prieto-Matias M. Swifold: Smith-waterman implementation on fpga with opencl for long dna sequences. BMC Syst Biol. 2018;12(5):96.","journal-title":"BMC Syst Biol"},{"issue":"5","key":"6521_CR30","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1093\/bioinformatics\/btad155","volume":"39","author":"S Diab","year":"2023","unstructured":"Diab S, Nassereldine A, Alser M, G\u00f3mez Luna J, Mutlu O, El Hajj I. A framework for high-throughput sequence alignment using real processing-in-memory systems. Bioinformatics. 2023;39(5):155.","journal-title":"Bioinformatics"},{"key":"6521_CR31","doi-asserted-by":"crossref","unstructured":"Doblas M, Shih PJ, Lostes-Cazorla O, Moreto M, Batten C, Marco-Sola S, et al. Heterogeneous architecture for universal sequence alignment acceleration. In: Proceedings of the 58th IEEE\/ACM International Symposium on Microarchitecture\u00ae. 2025. p. 1656\u201371.","DOI":"10.1145\/3725843.3756018"},{"issue":"5","key":"6521_CR32","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1145\/3712168","volume":"68","author":"Y Gu","year":"2025","unstructured":"Gu Y, Subramaniyan A, Dunn T, Khadem A, Chen K-Y, Paul S, et al. Gendp: A framework of dynamic programming acceleration for genome sequencing analysis. Commun ACM. 2025;68(5):81\u201390.","journal-title":"Commun ACM"},{"key":"6521_CR33","unstructured":"Cao Y, Gupta A, Liang J, Turakhia Y. Dp-hls: A high-level synthesis framework for accelerating dynamic programming algorithms in bioinformatics. 2024.arXiv:2411.03398 arXiv preprint."},{"issue":"12","key":"6521_CR34","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1093\/bioinformatics\/btad701","volume":"39","author":"Q Aguado-Puig","year":"2023","unstructured":"Aguado-Puig Q, Doblas M, Matzoros C, Espinosa A, Moure JC, Marco-Sola S, et al. Wfa-gpu: gap-affine pairwise read-alignment using gpus. Bioinformatics. 2023;39(12):701.","journal-title":"Bioinformatics"},{"key":"6521_CR35","doi-asserted-by":"crossref","unstructured":"Han Y, Kim S, Park S, Lee J. G 3sa: A gpu-accelerated gold standard genomics library for end-to-end sequence alignment. In: Proceedings of the 39th ACM International Conference on Supercomputing, pp. 173\u2013188 (2025)","DOI":"10.1145\/3721145.3729516"},{"key":"6521_CR36","doi-asserted-by":"publisher","unstructured":"Li H. Aligning sequence reads, clone sequences and assembly contigs with bwa-mem. 2013. https:\/\/doi.org\/10.48550\/ARXIV.1303.3997.","DOI":"10.48550\/ARXIV.1303.3997."},{"issue":"3","key":"6521_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead B, Trapnell C, Pop M, Salzberg SL. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 2009;10(3):25.","journal-title":"Genome Biol"},{"issue":"15","key":"6521_CR38","doi-asserted-by":"publisher","first-page":"1590","DOI":"10.1056\/NEJMra0706737","volume":"358","author":"BS Taylor","year":"2008","unstructured":"Taylor BS, Sobieszczyk ME, McCutchan FE, Hammer SM. The challenge of HIV-1 subtype diversity. N Engl J Med. 2008;358(15):1590\u2013602.","journal-title":"N Engl J Med"},{"issue":"4","key":"6521_CR39","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1093\/bioinformatics\/btr708","volume":"28","author":"W Huang","year":"2011","unstructured":"Huang W, Li L, Myers JR, Marth GT. Art: a next-generation sequencing read simulator. Bioinformatics. 2011;28(4):593\u20134. https:\/\/doi.org\/10.1093\/bioinformatics\/btr708.","journal-title":"Bioinformatics"},{"issue":"5","key":"6521_CR40","doi-asserted-by":"publisher","first-page":"427","DOI":"10.2174\/1570162x113116660064","volume":"11","author":"M Rao","year":"2013","unstructured":"Rao M, Peachman K, Kim J, Gao G, Alving C, Michael N, et al. Hiv-1 variable loop 2 and its importance in hiv-1 infection and vaccine development. Curr HIV Res. 2013;11(5):427\u201338. https:\/\/doi.org\/10.2174\/1570162x113116660064.","journal-title":"Curr HIV Res"},{"issue":"8","key":"6521_CR41","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1093\/bioinformatics\/btad487","volume":"39","author":"D Liu","year":"2023","unstructured":"Liu D, Steinegger M. Block aligner: an adaptive simd-accelerated aligner for sequences and position-specific scoring matrices. Bioinformatics. 2023;39(8):487.","journal-title":"Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-026-06521-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-026-06521-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-026-06521-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T12:34:49Z","timestamp":1782131689000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s12859-026-06521-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,21]]},"references-count":41,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["6521"],"URL":"https:\/\/doi.org\/10.1186\/s12859-026-06521-0","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,21]]},"assertion":[{"value":"5 January 2026","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare no conflict of interest.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"137"}}