{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:01:01Z","timestamp":1787313661461,"version":"build-2736575974"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"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":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Bioinformatic workflows frequently make use of automated genome assembly and protein clustering tools. At the core of most of these tools, a significant portion of execution time is spent in determining optimal local alignment between two sequences. This task is performed with the Smith-Waterman algorithm, which is a dynamic programming based method. With the advent of modern sequencing technologies and increasing size of both genome and protein databases, a need for faster Smith-Waterman implementations has emerged. Multiple SIMD strategies for the Smith-Waterman algorithm are available for CPUs. However, with the move of HPC facilities towards accelerator based architectures, a need for an efficient GPU accelerated strategy has emerged. Existing GPU based strategies have either been optimized for a specific type of characters (Nucleotides or Amino Acids) or for only a handful of application use-cases.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>In this paper, we present ADEPT, a new sequence alignment strategy for GPU architectures that is domain independent, supporting alignment of sequences from both genomes and proteins. Our proposed strategy uses GPU specific optimizations that do not rely on the nature of sequence. We demonstrate the feasibility of this strategy by implementing the Smith-Waterman algorithm and comparing it to similar CPU strategies as well as the fastest known GPU methods for each domain. ADEPT\u2019s driver enables it to scale across multiple GPUs and allows easy integration into software pipelines which utilize large scale computational systems. We have shown that the ADEPT based Smith-Waterman algorithm demonstrates a peak performance of 360 GCUPS and 497 GCUPs for protein based and DNA based datasets respectively on a single GPU node (8 GPUs) of the Cori Supercomputer. Overall ADEPT shows 10x faster performance in a node-to-node comparison against a corresponding SIMD CPU implementation.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>ADEPT demonstrates a performance that is either comparable or better than existing GPU strategies. We demonstrated the efficacy of ADEPT in supporting existing bionformatics software pipelines by integrating ADEPT in MetaHipMer a high-performance denovo metagenome assembler and PASTIS a high-performance protein similarity graph construction pipeline. Our results show 10% and 30% boost of performance in MetaHipMer and PASTIS respectively.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-020-03720-1","type":"journal-article","created":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T08:02:55Z","timestamp":1600156975000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["ADEPT: a domain independent sequence alignment strategy for gpu architectures"],"prefix":"10.1186","volume":"21","author":[{"given":"Muaaz G.","family":"Awan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jack","family":"Deslippe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aydin","family":"Buluc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oguz","family":"Selvitopi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven","family":"Hofmeyr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonid","family":"Oliker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katherine","family":"Yelick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,9,15]]},"reference":[{"key":"3720_CR1","volume-title":"2015 IEEE International Parallel and Distributed Processing Symposium","author":"E Georganas","year":"2015","unstructured":"Georganas E, Bulu\u00e7 A, Chapman J, Oliker L, Rokhsar D, Yelick K. meraligner: A fully parallel sequence aligner. In: 2015 IEEE International Parallel and Distributed Processing Symposium. Hyderabad International Convention Centre, Hyderabad: IEEE: 2015. p. 561\u201370."},{"key":"3720_CR2","volume-title":"SC\u201915: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"E Georganas","year":"2015","unstructured":"Georganas E, Bulu\u00e7 A, Chapman J, Hofmeyr S, Aluru C, Egan R, Oliker L, Rokhsar D, Yelick K. Hipmer: an extreme-scale de novo genome assembler. In: SC\u201915: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. Austin: IEEE: 2015. p. 1\u201311."},{"key":"3720_CR3","doi-asserted-by":"crossref","unstructured":"Ellis M, Guidi G, Bulu\u00e7 A, Oliker L, Yelick K. dibella: Distributed long read to long read alignment. In: Proceedings of the 48th International Conference on Parallel Processing. ACM: 2019. p. 1\u201311.","DOI":"10.1145\/3337821.3337919"},{"issue":"215","key":"3720_CR4","first-page":"1","volume":"5","author":"A Ba","year":"2012","unstructured":"Ba A, Yeh B, Van Dyk D, Davidson A, Andrews B, Weiss E, Moses A. Proteome-wide discovery of evolutionary conserved sequences in disordered regions. Sci Signal. 2012; 5(215):1\u20131.","journal-title":"Sci Signal"},{"issue":"1","key":"3720_CR5","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T Smith","year":"1981","unstructured":"Smith T, Waterman M, et al. Identification of common molecular subsequences. J Mol Biol. 1981; 147(1):195\u20137.","journal-title":"J Mol Biol"},{"issue":"3","key":"3720_CR6","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 Mol Biol. 1982; 162(3):705\u20138.","journal-title":"J Mol Biol"},{"issue":"17","key":"3720_CR7","doi-asserted-by":"publisher","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","volume":"25","author":"S Altschul","year":"1997","unstructured":"Altschul S, Madden T, Sch\u00e4ffer A, Zhang J, Zhang Z, Miller W, Lipman D. Gapped blast and psi-blast: a new generation of protein database search programs. Nucleic Acids Res. 1997; 25(17):3389\u2013402.","journal-title":"Nucleic Acids Res"},{"key":"3720_CR8","unstructured":"Madden T. The NCBI Handbook [Internet]. 2nd Edition: National Center for Biotechnology Information (US); 2013. https:\/\/www.ncbi.nlm.nih.gov\/books\/NBK143764\/."},{"issue":"1","key":"3720_CR9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1186\/1471-2105-12-221","volume":"12","author":"T Rognes","year":"2011","unstructured":"Rognes T. Faster smith-waterman database searches with inter-sequence simd parallelisation. BMC bioinformatics. 2011; 12(1):221.","journal-title":"BMC bioinformatics"},{"issue":"2","key":"3720_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1093\/bioinformatics\/13.2.145","volume":"13","author":"A Wozniak","year":"1997","unstructured":"Wozniak A. Using video-oriented instructions to speed up sequence comparison. Bioinformatics. 1997; 13(2):145\u201350.","journal-title":"Bioinformatics"},{"key":"3720_CR11","volume-title":"2014 14th IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing","author":"FdO Edans","year":"2014","unstructured":"Edans FdO, Miranda G, de Melo A, Martorell X, Ayguad\u00e9 E. Cudalign 3.0: Parallel biological sequence comparison in large gpu clusters. In: 2014 14th IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing. Chicago: IEEE: 2014. p. 160\u2013169."},{"issue":"8","key":"3720_CR12","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1093\/bioinformatics\/16.8.699","volume":"16","author":"T Rognes","year":"2000","unstructured":"Rognes T, Seeberg E. Six-fold speed-up of smith\u2013waterman sequence database searches using parallel processing on common microprocessors. Bioinformatics. 2000; 16(8):699\u2013706.","journal-title":"Bioinformatics"},{"issue":"2","key":"3720_CR13","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","volume":"23","author":"M Farrar","year":"2007","unstructured":"Farrar M. Striped smith\u2013waterman speeds database searches six times over other simd implementations. Bioinformatics. 2007; 23(2):156\u201361.","journal-title":"Bioinformatics"},{"issue":"1","key":"3720_CR14","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":"S2","key":"3720_CR15","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1186\/1471-2105-9-S2-S10","volume":"9","author":"S Manavski","year":"2008","unstructured":"Manavski S, Valle G. Cuda compatible gpu cards as efficient hardware accelerators for smith-waterman sequence alignment. BMC bioinformatics. 2008; 9(S2):10.","journal-title":"BMC bioinformatics"},{"issue":"1","key":"3720_CR16","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1186\/s12859-019-3086-9","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 bioinformatics. 2019; 20(1):520.","journal-title":"BMC bioinformatics"},{"key":"3720_CR17","unstructured":"Li H. Aligning sequence reads, clone sequences and assembly contigs with bwa-mem. arXiv preprint arXiv:1303.3997. 2013. q-bio.GN."},{"issue":"4","key":"3720_CR18","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead B, Salzberg S. Fast gapped-read alignment with bowtie 2. Nat Methods. 2012; 9(4):357.","journal-title":"Nat Methods"},{"key":"3720_CR19","volume-title":"SC18: International Conference for High Performance Computing, Networking, Storage and Analysis","author":"E Georganas","year":"2018","unstructured":"Georganas E, Egan R, Hofmeyr S, Goltsman E, Arndt B, Tritt A, Bulu\u00e7 A, Oliker L, Yelick K. Extreme scale de novo metagenome assembly. In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis. Dallas: IEEE: 2018. p. 122\u201334."},{"issue":"1","key":"3720_CR20","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/0471250953.bi1104s17","volume":"17","author":"M de la Bastide","year":"2007","unstructured":"de la Bastide M, McCombie W. Assembling genomic dna sequences with phrap. Curr Protoc Bioinforma. 2007; 17(1):11\u20134.","journal-title":"Curr Protoc Bioinforma"},{"issue":"11","key":"3720_CR21","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1038\/nbt.3988","volume":"35","author":"M Steinegger","year":"2017","unstructured":"Steinegger M, S\u00f6ding J. Mmseqs2 enables sensitive protein sequence searching for the analysis of massive data sets. Nat Biotechnol. 2017; 35(11):1026.","journal-title":"Nat Biotechnol"},{"issue":"1","key":"3720_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1038\/nmeth.3176","volume":"12","author":"B Buchfink","year":"2015","unstructured":"Buchfink B, Xie C, Huson D. Fast and sensitive protein alignment using DIAMOND. Nat Methods. 2015; 12(1):59.","journal-title":"Nat Methods"},{"issue":"6","key":"3720_CR23","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1038\/nmeth0610-419","volume":"7","author":"T Wittkop","year":"2010","unstructured":"Wittkop T, Emig D, Lange S, Rahmann S, Albrecht M, Morris J, B\u00f6cker S, Stoye J, Baumbach J. Partitioning biological data with transitivity clustering. Nature methods. 2010; 7(6):419.","journal-title":"Nature methods"},{"issue":"6","key":"3720_CR24","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1093\/nar\/gkx1313","volume":"46","author":"A Azad","year":"2018","unstructured":"Azad A, Pavlopoulos G, Ouzounis C, Kyrpides N, Bulu\u00e7 A. HipMCL: A high-performance parallel implementation of the Markov clustering algorithm for large-scale networks. Nucleic Acids Res. 2018; 46(6):33\u201333.","journal-title":"Nucleic Acids Res"},{"issue":"7","key":"3720_CR25","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.1093\/nar\/30.7.1575","volume":"30","author":"A Enright","year":"2002","unstructured":"Enright A, Van Dongen S, Ouzounis C. An efficient algorithm for large-scale detection of protein families. Nucleic Acids Res. 2002; 30(7):1575\u201384.","journal-title":"Nucleic Acids Res"},{"key":"3720_CR26","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 T, Ehrhardt M, Hauswedell H, Mehringer S, Rahn R, Kim J, Pockrandt C, Winkler J, Siragusa E, 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"},{"key":"3720_CR27","doi-asserted-by":"crossref","unstructured":"Zhao M, Lee W-P, Garrison E, Marth G. Ssw library: an simd smith-waterman c\/c++ library for use in genomic applications. PLoS ONE. 2013; 8(12).","DOI":"10.1371\/journal.pone.0082138"},{"key":"3720_CR28","unstructured":"NVIDIA T. V100 GPU architecture: NVIDIA; 2017. https:\/\/images.nvidia.com\/content\/volta-architecture\/pdf\/volta-architecturewhitepaper.pdf ."},{"key":"3720_CR29","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.compbiomed.2018.08.015","volume":"101","author":"M Awan","year":"2018","unstructured":"Awan M, Eslami T, Saeed F. Gpu-daemon: Gpu algorithm design, data management & optimization template for array based big omics data. Comput Biol Med. 2018; 101:163\u201373.","journal-title":"Comput Biol Med"},{"key":"3720_CR30","unstructured":"NVIDIA. NVIDIA Developer Blog. https:\/\/devblogs.nvidia.com\/faster-parallel-reductions-kepler\/. Accessed 06 Apr 2020."},{"issue":"1","key":"3720_CR31","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/0471250953.bi0305s43","volume":"43","author":"W Pearson","year":"2013","unstructured":"Pearson W. Selecting the right similarity-scoring matrix. Curr Protoc Bioinforma. 2013; 43(1):3\u20135.","journal-title":"Curr Protoc Bioinforma"},{"key":"3720_CR32","unstructured":"Oak Ridge National Laboratory. Summit, Specifications and Features. https:\/\/www.olcf.ornl.gov\/olcf-resources\/compute-systems\/summit\/. Accessed 22 July 2020."},{"key":"3720_CR33","unstructured":"National Energy Research Scientific Computing Center. Perlmutter. https:\/\/www.nersc.gov\/systems\/perlmutter\/. Accessed 22 July 2020."},{"key":"3720_CR34","unstructured":"NVIDIA. NVBIO Library. https:\/\/developer.nvidia.com\/nvbio. Accessed 22 July 2020."},{"issue":"20","key":"3720_CR35","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"},{"issue":"6","key":"3720_CR36","doi-asserted-by":"publisher","first-page":"1882","DOI":"10.1111\/1462-2920.12086","volume":"15","author":"M Shakya","year":"2013","unstructured":"Shakya M, Quince C, Campbell J, Yang Z, Schadt C, Podar M. Comparative metagenomic and rRNA microbial diversity characterization using archaeal and bacterial synthetic communities. Environ Microbiol. 2013; 15(6):1882\u201399. https:\/\/doi.org\/10.1111\/1462-2920.12086.","journal-title":"Environ Microbiol"},{"key":"3720_CR37","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1093\/nar\/gkt1240","volume":"42","author":"N Fox","year":"2014","unstructured":"Fox N, Brenner S, Chandonia J. SCOPe: Structural Classification of Proteins\u2013extended, integrating SCOP and ASTRAL data and classification of new structures. Nucleic Acids Res. 2014; 42:304\u20139. Database issue.","journal-title":"Nucleic Acids Res"},{"key":"3720_CR38","doi-asserted-by":"crossref","unstructured":"Selvitopi O, Ekanayake S, Guidi G, Pavlopoulos G, Azad A, Bulu\u00e7 A. Distributed many-to-many protein sequence alignment using sparse matrices. In: Proceedings of the 2020 ACM\/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis. SC \u201920. 3001 in press. https:\/\/sc20.supercomputing.org\/presentation\/?id=pap572&sess=sess152.","DOI":"10.1109\/SC41405.2020.00079"},{"issue":"1","key":"3720_CR39","doi-asserted-by":"publisher","first-page":"4297","DOI":"10.1002\/cpe.4297","volume":"30","author":"D Doerfler","year":"2018","unstructured":"Doerfler D, Austin B, Cook B, Deslippe J, Kandalla K, Mendygral P. Evaluating the networking characteristics of the cray xc-40 intel knights landing-based cori supercomputer at nersc. Concurr Comput Pract Exp. 2018; 30(1):4297.","journal-title":"Concurr Comput Pract Exp"},{"key":"3720_CR40","unstructured":"National Energy Research Scientific Computing Center. Cori Configurations. https:\/\/docs.nersc.gov\/systems\/cori\/. Accessed 02 May 2020."},{"key":"3720_CR41","unstructured":"National Energy Research Scientific Computing Center. Cori GPU Nodes, Hardware Info. https:\/\/docs-dev.nersc.gov\/cgpu\/hardware\/. Accessed 02 May 2020."},{"issue":"1","key":"3720_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-020-67416-5","volume":"10","author":"S Hofmeyr","year":"2020","unstructured":"Hofmeyr S, Egan R, Georganas E, Copeland A, Riley R, Clum A, Eloe-Fadrosh E, Roux S, Goltsman E, Bulu\u00e7 A, et al. Terabase-scale metagenome coassembly with metahipmer. Sci Rep. 2020; 10(1):1\u201311.","journal-title":"Sci Rep"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03720-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-020-03720-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03720-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T06:28:38Z","timestamp":1696660118000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-020-03720-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,15]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["3720"],"URL":"https:\/\/doi.org\/10.1186\/s12859-020-03720-1","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,15]]},"assertion":[{"value":"20 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2020","order":3,"name":"first_online","label":"First Online","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":"406"}}