{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T17:17:35Z","timestamp":1782926255876,"version":"3.54.5"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,10,6]],"date-time":"2015-10-06T00:00:00Z","timestamp":1444089600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2015,10,6]],"date-time":"2015-10-06T00:00:00Z","timestamp":1444089600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["15H01687"],"award-info":[{"award-number":["15H01687"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["15K12008"],"award-info":[{"award-number":["15K12008"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1186\/s12859-015-0744-4","type":"journal-article","created":{"date-parts":[[2015,10,6]],"date-time":"2015-10-06T03:34:10Z","timestamp":1444102450000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Accelerating the Smith-Waterman algorithm with interpair pruning and band optimization for the all-pairs comparison of base sequences"],"prefix":"10.1186","volume":"16","author":[{"given":"Daiki","family":"Okada","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fumihiko","family":"Ino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kenichi","family":"Hagihara","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,10,6]]},"reference":[{"issue":"1","key":"744_CR1","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 Mol Biol. 1981; 147(1):195\u20137.","journal-title":"J Mol Biol"},{"issue":"S10","key":"744_CR2","first-page":"9","volume":"9","author":"SA Manavski","year":"2008","unstructured":"Manavski SA, Valle G. CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinforma. 2008; 9(S10):9.","journal-title":"BMC Bioinforma"},{"key":"744_CR3","doi-asserted-by":"crossref","unstructured":"de O. Sandes EF, de Melo ACMA. CUDAlign: Using GPU to accelerate the comparison of megabase genomic sequences. In: Proc. 15th ACM SIGPLAN Symp. Principles and Practice of Parallel Programming (PPoPP\u201910). ACM: 2010. p. 137\u201346.","DOI":"10.1145\/1693453.1693473"},{"issue":"181","key":"744_CR4","first-page":"17","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 Bioinforma. 2011; 12(181):17.","journal-title":"BMC Bioinforma"},{"issue":"19","key":"744_CR5","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#\u2013gpu-enabled exact alignments on genome scale. Bioinformatics. 2013; 29(19):2494\u20135.","journal-title":"Bioinformatics"},{"issue":"2","key":"744_CR6","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","volume":"23","author":"M Farrar","year":"2007","unstructured":"Farrar M. Striped Smith-Waterman speeds database searches six times over other SIMD implementations. Bioinformatics. 2007; 23(2):156\u201361.","journal-title":"Bioinformatics"},{"issue":"107","key":"744_CR7","first-page":"4","volume":"1","author":"A Szalkowski","year":"2008","unstructured":"Szalkowski A, Ledergerber C, Kr\u00e4henb\u00fchl P, Dessimoz C. SWPS3 \u2014 fast multi-threaded vectorized Smith-Waterman for IBM Cell\/B.E. and x86\/SSE2. BMC Res Notes. 2008; 1(107):4.","journal-title":"BMC Res Notes"},{"issue":"221","key":"744_CR8","first-page":"11","volume":"12","author":"T Rognes","year":"2010","unstructured":"Rognes T. Faster Smith-Waterman database searches with inter-sequence SIMD parallelisation. BMC Bioinforma. 2010; 12(221):11.","journal-title":"BMC Bioinforma"},{"issue":"185","key":"744_CR9","first-page":"7","volume":"8","author":"IT Li","year":"2007","unstructured":"Li IT, Shum W, Truong K. 160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA). BMC Bioinforma. 2007; 8(185):7.","journal-title":"BMC Bioinforma"},{"key":"744_CR10","doi-asserted-by":"crossref","unstructured":"Liu Y, Schmidt B. SWAPHI: Smith-Waterman protein database search on Xeon Phi coprocessors. In: Proc. 25th IEEE Int\u2019l Conf. Application-specific Systems, Architectures and Processors (ASAP\u201914). IEEE: 2014. p. 184\u20135.","DOI":"10.1109\/ASAP.2014.6868657"},{"issue":"2","key":"744_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/MM.2008.31","volume":"28","author":"E Lindholm","year":"2008","unstructured":"Lindholm E, Nickolls J, Oberman S, Montrym J. NVIDIA Tesla: A unified graphics and computing architecture. IEEE Micro. 2008; 28(2):39\u201355.","journal-title":"IEEE Micro"},{"issue":"5","key":"744_CR12","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1109\/JPROC.2008.917757","volume":"96","author":"JD Owens","year":"2008","unstructured":"Owens JD, Houston M, Luebke D, Green S, Stone JE, Phillips JC. GPU computing. Proc IEEE. 2008; 96(5):879\u201399.","journal-title":"Proc IEEE"},{"issue":"4","key":"744_CR13","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1109\/TPDS.2011.239","volume":"23","author":"F Ino","year":"2012","unstructured":"Ino F, Munekawa Y, Hagihara K. Sequence homology search using fine grained cycle sharing of idle GPUs. IEEE Trans Parallel Distrib Syst. 2012; 23(4):751\u20139.","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"3","key":"744_CR14","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1109\/JBHI.2014.2310745","volume":"18","author":"K Ikeda","year":"2014","unstructured":"Ikeda K, Ino F, Hagihara K. Efficient acceleration of mutual information computation for nonrigid registration using CUDA. IEEE J Biomed Health Informa. 2014; 18(3):956\u201368.","journal-title":"IEEE J Biomed Health Informa"},{"issue":"1","key":"744_CR15","first-page":"11","volume":"4","author":"EW Myers","year":"1988","unstructured":"Myers EW, Miller W. Optimal alignments in linear space. Comput Appl Biosci. 1988; 4(1):11\u20137.","journal-title":"Comput Appl Biosci"},{"issue":"5","key":"744_CR16","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1109\/TPDS.2012.194","volume":"24","author":"EF de O. Sandes","year":"2013","unstructured":"de O. Sandes EF, de Melo ACMA. Retrieving Smith-Waterman alignments with optimizations for megabase biological sequences using GPU. IEEE Trans Parallel Distrib Syst. 2013; 24(5):1009\u201321.","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"744_CR17","doi-asserted-by":"crossref","unstructured":"de O. Sandes EF, Miranda G, de Melo ACMA, Martorell X, Ayguad\u00e9 E. Cudalign 3.0: Parallel biological sequence comparison in large gpu clusters. In: Proc. 14th IEEE\/ACM Int\u2019l Symp. Cluster, Cloud and Grid Computing (CCGrid\u201914). IEEE: 2014. p. 160\u20139.","DOI":"10.1109\/CCGrid.2014.18"},{"issue":"4","key":"744_CR18","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"DF Feng","year":"1987","unstructured":"Feng DF, Doolittle RF. Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J Mol Evol. 1987; 25(4):351\u201360.","journal-title":"J Mol Evol"},{"issue":"5","key":"744_CR19","first-page":"481","volume":"8","author":"KM Chao","year":"1992","unstructured":"Chao KM, Pearson WR, Miller W. Aligning two sequences within a specified diagonal band. Comput Appl Biosci. 1992; 8(5):481\u20137.","journal-title":"Comput Appl Biosci"},{"issue":"22","key":"744_CR20","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"JD Thompson","year":"1994","unstructured":"Thompson JD, Higgins DG, Gibson TJ. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res. 1994; 22(22):4673\u201380.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"744_CR21","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins DG, Heringa J. T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol. 2000; 302(1):205\u201317.","journal-title":"J Mol Biol"},{"issue":"1","key":"744_CR22","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0022-2836(87)90521-3","volume":"196","author":"D Bashford","year":"1987","unstructured":"Bashford D, Chothia C, Lesk AM. Determinants of a protein fold: Unique features of the globin amino acid sequences. J Mol Biol. 1987; 196(1):199\u2013216.","journal-title":"J Mol Biol"},{"issue":"1","key":"744_CR23","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.jpdc.2012.04.004","volume":"73","author":"J Blazewicz","year":"2013","unstructured":"Blazewicz J, Frohmberg W, Kierzynka M, Wojciechowski P. G-MSA\u2013A GPU-based, fast and accurate algorithm for multiple sequence alignment. J Parallel Distrib Comput. 2013; 73(1):32\u201341.","journal-title":"J Parallel Distrib Comput"},{"issue":"1\u20133","key":"744_CR24","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E Ukkonen","year":"1985","unstructured":"Ukkonen E. Algorithms for approximate string matching. Inf Control. 1985; 64(1\u20133):100\u201318.","journal-title":"Inf Control"},{"key":"744_CR25","unstructured":"Klimovitski A. Using SSE and SSE2: Misconceptions and reality. In: Intel Developer Update Magazine. Intel: 2001."},{"key":"744_CR26","unstructured":"Intel Corporation: Intel Xeon Phi Product Family. \n                    http:\/\/www.intel.com\/content\/www\/us\/en\/processors\/xeon\/xeon-phi-detail.html\n                    \n                  . Accessed 18 Sep 2015."},{"issue":"9","key":"744_CR27","doi-asserted-by":"publisher","first-page":"1270","DOI":"10.1109\/TPDS.2007.1059","volume":"18","author":"W Liu","year":"2007","unstructured":"Liu W, Schmidt B, Voss G, M\u00fcller-Wittig W. Streaming algorithms for biological sequence alignment on GPUs. IEEE Trans Parallel Distrib Syst. 2007; 18(9):1270\u201381.","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"93","key":"744_CR28","first-page":"12","volume":"3","author":"Y Liu","year":"2010","unstructured":"Liu Y, Schmidt B, Maskell DL. CUDASW++2.0: enhanced Smith-Waterman protein database search on cuda-enabled GPUs based on SIMT and virtualized SIMD abstractions. BMC Res Notes. 2010; 3(93):12.","journal-title":"BMC Res Notes"},{"issue":"6","key":"744_CR29","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1587\/transinf.E93.D.1479","volume":"E93-D","author":"Y Munekawa","year":"2010","unstructured":"Munekawa Y, Ino F, Hagihara K. Accelerating Smith-Waterman algorithm for biological database search on CUDA-compatible GPUs. IEICE Trans Inf Syst. 2010; E93-D(6):1479\u201388.","journal-title":"IEICE Trans Inf Syst"},{"issue":"3","key":"744_CR30","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":"6","key":"744_CR31","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS. A linear space algorithm for computing maximal common subsequences. Commun ACM. 1975; 18(6):341\u20133.","journal-title":"Commun ACM"},{"key":"744_CR32","unstructured":"NVIDIA Corporation. CUDA C Programming Guide Version 6.5. 2014. \n                    http:\/\/docs.nvidia.com\/cuda\/pdf\/CUDA_C_Programming_Guide.pdf\n                    \n                  . Accessed 18 Sep 2015."},{"issue":"3","key":"744_CR33","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 Mol Biol. 1970; 48(3):443\u201353.","journal-title":"J Mol Biol"},{"key":"744_CR34","unstructured":"National Center for Biotechnology Information: NCBI data. 2014. \n                    http:\/\/www.ncbi.nlm.nih.gov\/\n                    \n                  . Accessed 18 Sep 2015."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0744-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-015-0744-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0744-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T10:45:49Z","timestamp":1589453149000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-015-0744-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,6]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["744"],"URL":"https:\/\/doi.org\/10.1186\/s12859-015-0744-4","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,6]]},"assertion":[{"value":"3 June 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"321"}}