{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:07:43Z","timestamp":1782968863365,"version":"3.54.5"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Due the computational complexity of sequence alignment algorithms, various accelerated solutions have been proposed to speedup this analysis. NVBIO is the only available GPU library that accelerates sequence alignment of high-throughput NGS data, but has limited performance. In this article we present <jats:italic>GASAL2<\/jats:italic>, a GPU library for aligning DNA and RNA sequences that outperforms existing CPU and GPU libraries.<\/jats:p>\n              <\/jats:sec>\n              <jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>The GASAL2 library provides specialized, accelerated kernels for local, global and all types of semi-global alignment. Pairwise sequence alignment can be performed with and without traceback. GASAL2 outperforms the fastest CPU-optimized SIMD implementations such as SeqAn and Parasail, as well as NVIDIA\u2019s own GPU-based library known as NVBIO. GASAL2 is unique in performing sequence packing on GPU, which is up to 750x faster than NVBIO. Overall on Geforce GTX 1080 Ti GPU, GASAL2 is up to 21x faster than Parasail on a dual socket hyper-threaded Intel Xeon system with 28 cores and up to 13x faster than NVBIO with a query length of up to 300 bases and 100 bases, respectively. GASAL2 alignment functions are asynchronous\/non-blocking and allow full overlap of CPU and GPU execution. The paper shows how to use GASAL2 to accelerate BWA-MEM, speeding up the local alignment by 20x, which gives an overall application speedup of 1.3x vs. CPU with up to 12 threads.<\/jats:p>\n              <\/jats:sec>\n              <jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>The library provides high performance APIs for local, global and semi-global alignment that can be easily integrated into various bioinformatics tools.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-019-3086-9","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T18:24:53Z","timestamp":1572027893000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":65,"title":["GASAL2: a GPU accelerated sequence alignment library for high-throughput NGS data"],"prefix":"10.1186","volume":"20","author":[{"given":"Nauman","family":"Ahmed","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"L\u00e9vy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shanshan","family":"Ren","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hamid","family":"Mushtaq","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Koen","family":"Bertels","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zaid","family":"Al-Ars","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,10,25]]},"reference":[{"key":"3086_CR1","unstructured":"Li H. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. arXiv. 2013."},{"key":"3086_CR2","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead B, S S. Fast gapped-read alignment with Bowtie 2. Nat Methods. 2012; 9:357\u201359.","journal-title":"Nat Methods"},{"key":"3086_CR3","unstructured":"Huang X, Yang S-P. Generating a Genome Assembly with PCAP. 2002."},{"key":"3086_CR4","unstructured":"de la Bastide M, McCombie WR. Assembling Genomic DNA Sequences with PHRAP. 2002."},{"issue":"11","key":"3086_CR5","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1093\/bioinformatics\/btr170","volume":"27","author":"L Salmela","year":"2011","unstructured":"Salmela L, Schr\u00f6der J. Correcting errors in short reads by multiple alignments. Bioinformatics. 2011; 27(11):1455\u201361.","journal-title":"Bioinformatics"},{"issue":"7","key":"3086_CR6","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1101\/gr.111351.110","volume":"21","author":"W-C Kao","year":"2011","unstructured":"Kao W-C, Chan AH, Song YS. ECHO: a reference-free short-read error correction algorithm. Genome Res. 2011; 21(7):1181\u201392.","journal-title":"Genome Res"},{"key":"3086_CR7","doi-asserted-by":"crossref","unstructured":"Poplin R, et al. Scaling accurate genetic variant discovery to tens of thousands of samples. bioRxiv. 2017.","DOI":"10.1101\/201178"},{"issue":"3","key":"3086_CR8","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mole Biol. 1970; 48(3):443\u201353.","journal-title":"J Mole Biol"},{"issue":"1","key":"3086_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS. Identification of common molecular subsequences. J Mole Biol. 1981; 147(1):195\u20137.","journal-title":"J Mole Biol"},{"issue":"3","key":"3086_CR10","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O. An improved algorithm for matching biological sequences. J Mole Biol. 1982; 162(3):705\u20138.","journal-title":"J Mole Biol"},{"key":"3086_CR11","doi-asserted-by":"crossref","unstructured":"Liu Y, Huang W, Johnson J, Vaidya S. In: Alexandrov VN, van Albada GD, Sloot PMA, Dongarra J, (eds).GPU Accelerated Smith-Waterman. Berlin, Heidelberg: Springer; 2006, pp. 188\u201395.","DOI":"10.1007\/11758549_29"},{"issue":"1","key":"3086_CR12","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 Bioinformatics. 2013; 14(1):117.","journal-title":"BMC Bioinformatics"},{"issue":"1","key":"3086_CR13","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1186\/1756-0500-4-261","volume":"4","author":"L Hasan","year":"2011","unstructured":"Hasan L, Kentie M, Al-Ars Z. DOPA: GPU-based protein alignment using database and memory access optimizations. BMC Res Notes. 2011; 4(1):261.","journal-title":"BMC Res Notes"},{"key":"3086_CR14","doi-asserted-by":"publisher","first-page":"117693431876054","DOI":"10.1177\/1176934318760543","volume":"14","author":"S Ren","year":"2018","unstructured":"Ren S, Bertels K, Al-Ars Z. Efficient Acceleration of the Pair-HMMs Forward Algorithm for GATK HaplotypeCaller on Graphics Processing Units. Evol Bioinforma. 2018; 14:1176934318760543.","journal-title":"Evol Bioinforma"},{"key":"3086_CR15","doi-asserted-by":"crossref","unstructured":"Ren S, Ahmed N, Bertels K, Al-Ars Z. An Efficient GPU-Based de Bruijn Graph Construction Algorithm for Micro-Assembly. In: 2018 IEEE 18th International Conference on Bioinformatics and Bioengineering (BIBE): 2018. p. 67\u201372.","DOI":"10.1109\/BIBE.2018.00020"},{"key":"3086_CR16","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.imu.2017.08.001","volume":"9","author":"T Kalaiselvi","year":"2017","unstructured":"Kalaiselvi T, Sriramakrishnan P, Somasundaram K. Survey of using gpu cuda programming model in medical image analysis. Informa Med Unlocked. 2017; 9:133\u201344.","journal-title":"Informa Med Unlocked"},{"issue":"2","key":"3086_CR17","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/j.bbe.2019.02.002","volume":"39","author":"P Sriramakrishnan","year":"2019","unstructured":"Sriramakrishnan P, Kalaiselvi T, Rajeswaran R. Modified local ternary patterns technique for brain tumour segmentation and volume estimation from mri multi-sequence scans with gpu cuda machine. Biocyber Biomed Eng. 2019; 39(2):470\u201387.","journal-title":"Biocyber Biomed Eng"},{"key":"3086_CR18","doi-asserted-by":"crossref","unstructured":"Bhosale P, Staring M, Al-Ars Z, Berendsen FF. GPU-based stochastic-gradient optimization for non-rigid medical image registration in time-critical applications. In: SPIE Medical Imaging 2018: 2018.","DOI":"10.1117\/12.2293098"},{"issue":"1","key":"3086_CR19","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1186\/1471-2105-12-181","volume":"12","author":"J Blazewicz","year":"2011","unstructured":"Blazewicz J, Frohmberg W, Kierzynka M, Pesch E, Wojciechowski P. Protein alignment algorithms with an efficient backtracking routine on multiple GPUs. BMC Bioinformatics. 2011; 12(1):181.","journal-title":"BMC Bioinformatics"},{"issue":"4","key":"3086_CR20","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1002\/cpe.3371","volume":"27","author":"Y Liu","year":"2015","unstructured":"Liu Y, Schmidt B. GSWABE: faster GPU-accelerated sequence alignment with optimal alignment retrieval for short DNA sequences. Concurr Comput: Pract Exp. 2015; 27(4):958\u201372.","journal-title":"Concurr Comput: Pract Exp"},{"key":"3086_CR21","unstructured":"Pantaleoni J, Subtil N. NVBIO. 2015. \nhttps:\/\/nvlabs.github.io\/nvbio\n\n. Accessed 1 October, 2017."},{"key":"3086_CR22","doi-asserted-by":"crossref","unstructured":"Ahmed N, Mushtaq H, Bertels K, Al-Ars Z. GPU accelerated API for alignment of genomics sequencing data. In: 2017 IEEE International Conference on Bioinformatics and Biomedicine (BIBM): 2017. p. 510\u20135.","DOI":"10.1109\/BIBM.2017.8217699"},{"key":"3086_CR23","unstructured":"Li H. wgsim: Reads simulator. \nhttps:\/\/github.com\/lh3\/wgsim\n\n. Accessed 1 October, 2017."},{"issue":"20","key":"3086_CR24","doi-asserted-by":"publisher","first-page":"3437","DOI":"10.1093\/bioinformatics\/bty380","volume":"34","author":"M Ehrhardt","year":"2018","unstructured":"Ehrhardt M, Rahn R, Reinert K, Budach S, Costanza P, Hancox J. Generic accelerated sequence alignment in SeqAn using vectorization and multi-threading. Bioinformatics. 2018; 34(20):3437\u201345.","journal-title":"Bioinformatics"},{"key":"3086_CR25","unstructured":"R R. DP Bench - A benchmark tool for SeqAn\u2019s alignment engine."},{"key":"3086_CR26","unstructured":"Chaos A. Klib: a Generic Library in C. \nhttps:\/\/github.com\/attractivechaos\/klib\n\n. Accessed 2 January, 2019."},{"key":"3086_CR27","doi-asserted-by":"crossref","unstructured":"Zhao M, et al. SSW library: An SIMD smith-waterman c\/c++ library for use in genomic applications. PLoS ONE. 2013;8.","DOI":"10.1371\/journal.pone.0082138"},{"issue":"1","key":"3086_CR28","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 Bioinformatics. 2016; 17(1):1\u201311.","journal-title":"BMC Bioinformatics"},{"issue":"9","key":"3086_CR29","doi-asserted-by":"publisher","first-page":"1394","DOI":"10.1093\/bioinformatics\/btw753","volume":"33","author":"M \u0160o\u0161i\u0107","year":"2017","unstructured":"\u0160o\u0161i\u0107 M, \u0160iki\u0107 M. Edlib: a C\/C++ library for fast, exact sequence alignment using edit distance. Bioinformatics. 2017; 33(9):1394\u20135.","journal-title":"Bioinformatics"},{"issue":"22","key":"3086_CR30","doi-asserted-by":"publisher","first-page":"3166","DOI":"10.1093\/bioinformatics\/btu507","volume":"30","author":"G Benson","year":"2014","unstructured":"Benson G, Loving J, Hernandez Y. BitPAl: a bit-parallel, general integer-scoring sequence alignment algorithm. Bioinformatics. 2014; 30(22):3166\u201373.","journal-title":"Bioinformatics"},{"key":"3086_CR31","doi-asserted-by":"crossref","unstructured":"Lan H, Zhang J, Chan Y, Liu W, Shang Y, Schmidt B. BGSA: a bit-parallel global sequence alignment toolkit for multi-core and many-core architectures. 2018.","DOI":"10.1093\/bioinformatics\/bty930"},{"issue":"1","key":"3086_CR32","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1093\/bioinformatics\/4.1.11","volume":"4","author":"EW Myers","year":"1988","unstructured":"Myers EW, Miller W. Optimal alignments in linear space. Bioinformatics. 1988; 4(1):11\u20137.","journal-title":"Bioinformatics"}],"updated-by":[{"DOI":"10.1186\/s12859-019-3185-7","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2019,11,19]],"date-time":"2019-11-19T00:00:00Z","timestamp":1574121600000}}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-3086-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-019-3086-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-3086-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T23:09:22Z","timestamp":1603494562000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-019-3086-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,25]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["3086"],"URL":"https:\/\/doi.org\/10.1186\/s12859-019-3086-9","relation":{"correction":[{"id-type":"doi","id":"10.1186\/s12859-019-3185-7","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,25]]},"assertion":[{"value":"2 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2019","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Following publication of the original article [1], the author requested changes to the figures 4, 7, 8, 9, 12 and 14 to align these with the text. The corrected figures are supplied below.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"520"}}