{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T06:26:59Z","timestamp":1742970419782,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642551949"},{"type":"electronic","value":"9783642551956"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-55195-6_23","type":"book-chapter","created":{"date-parts":[[2014,5,7]],"date-time":"2014-05-07T14:55:32Z","timestamp":1399474532000},"page":"247-257","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Faster GPU-Accelerated Smith-Waterman Algorithm with Alignment Backtracking for Short DNA Sequences"],"prefix":"10.1007","author":[{"given":"Yongchao","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bertil","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,5,8]]},"reference":[{"key":"23_CR1","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.: Identification of common molecular subsequences. J. Mol. Biol. 147, 195\u2013197 (1981)","journal-title":"J. Mol. Biol."},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"707","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. 162, 707\u2013708 (1982)","journal-title":"J. Mol. Biol."},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","volume":"85","author":"WR Pearson","year":"1988","unstructured":"Pearson, W.R., Lipman, D.J.: Improved tools for biological sequence comparison. Proc. Nat. Acad. Sci. USA 85, 2444\u20132448 (1988)","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215, 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"JD Thompson","year":"1994","unstructured":"Thompson, J.D., Higgins, D.G., Gibson, T.J.: CLUSTALW: improving the sensitivity of progressive multiple sequence alignment through sequence Weighting, position-specific gap penalties and weight matrix choice. Nucleic Acid Res. 22, 4673\u20134680 (1994)","journal-title":"Nucleic Acid Res."},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"1958","DOI":"10.1093\/bioinformatics\/btq338","volume":"26","author":"Y Liu","year":"2010","unstructured":"Liu, Y., Schmidt, B., Maskell, D.L.: MSAProbs: multiple sequence alignment based on pair hidden Markov models and partition function posterior probabilities. Bioinformatics 26, 1958\u20131964 (2010)","journal-title":"Bioinformatics"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"1830","DOI":"10.1093\/bioinformatics\/bts276","volume":"28","author":"Y Liu","year":"2012","unstructured":"Liu, Y., Schmidt, B., Maskell, D.L.: CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform. Bioinformatics 28, 1830\u20131837 (2012)","journal-title":"Bioinformatics"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1186\/1471-2105-13-196","volume":"13","author":"N Alachiotis","year":"2012","unstructured":"Alachiotis, N., Berger, S.A., Stamatakis, A.: Coupling SIMD and SIMT architectures to boost performance of a phylogeny-aware alignment kernel. BMC Bioinform. 13, 196 (2012)","journal-title":"BMC Bioinform."},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1093\/bioinformatics\/bts061","volume":"28","author":"CM Liu","year":"2011","unstructured":"Liu, C.M., Wong, T., Wu, E., Luo, R., Yiu, S.M., Li, Y., Wang, B., Yu, C., Chu, X., Zhao, K., Li, R., Lam, T.W.: SOAP3: ultra-fast GPU-based parallel alignment tool for short reads. Bioinformatics 28, 878\u2013879 (2011)","journal-title":"Bioinformatics"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"S3","DOI":"10.1186\/1471-2105-11-S12-S3","volume":"11","author":"J Qiu","year":"2010","unstructured":"Qiu, J., Ekanayake, J., Gunarathne, T., Choi, J.Y., Bae, S.H., Li, H., Zhang, B., Wu, T.L., Ruan, Y., Ekanayake, S., Hughes, A., Fox, G.: Hybrid cloud and cluster computing paradigms for life science applications. BMC Bioinform. 11, S3 (2010)","journal-title":"BMC Bioinform."},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1186\/1756-0500-2-73","volume":"2","author":"Y Liu","year":"2009","unstructured":"Liu, Y., Maskell, D.L., Schmidt, B.: CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units. BMC Res. Notes 2, 73 (2009)","journal-title":"BMC Res. Notes"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"3431","DOI":"10.1093\/bioinformatics\/bti508","volume":"21","author":"T Oliver","year":"2005","unstructured":"Oliver, T., Schmidt, B., Nathan, D., Clemens, R., Maskell, D.L.: Using reconfigurable hardware to accelerate multiple sequence alignment with ClustalW. Bioinformatics 21, 3431\u20133432 (2005)","journal-title":"Bioinformatics"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1109\/TCSII.2005.853340","volume":"52","author":"T Oliver","year":"2005","unstructured":"Oliver, T., Schmidt, B., Maskell, D.L.: Reconfigurable architectures for bio-sequence database scanning on FPGAs. IEEE Trans. Circuit Syst. II 52, 851\u2013855 (2005)","journal-title":"IEEE Trans. Circuit Syst. II"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"I85","DOI":"10.1186\/1471-2105-8-85","volume":"8","author":"TI Li","year":"2007","unstructured":"Li, T.I., Shum, W., Truong, K.: 160-fold acceleration of the Smith-Waterman algorithm using a Field Programmable Gate Array (FPGA). BMC Bioinform. 8, I85 (2007)","journal-title":"BMC Bioinform."},{"key":"23_CR15","first-page":"145","volume":"13","author":"A Wozniak","year":"1997","unstructured":"Wozniak, A.: Using video-oriented instructions to speed up sequence comparison. Comput. Appl. Biosci. 13, 145\u2013150 (1997)","journal-title":"Comput. Appl. Biosci."},{"key":"23_CR16","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 speedup of Smith-Waterman sequence database searches using parallel processing on common microprocessors. Bioinformatics 16, 699\u2013706 (2000)","journal-title":"Bioinformatics"},{"key":"23_CR17","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 23, 156\u2013161 (2007)","journal-title":"Bioinformatics"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Alpern, B., Carter, L., Gatlin, K.S.: Microparallelism and high performance protein matching. In: Proceedings of the 1995 ACM\/IEEE Supercomputing Conference (1995)","DOI":"10.1145\/224170.224222"},{"key":"23_CR19","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 parallelization. BMC Bioinform. 12, 221 (2011)","journal-title":"BMC Bioinform."},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1186\/1471-2105-9-377","volume":"9","author":"A Wirawan","year":"2008","unstructured":"Wirawan, A., Kwoh, C.K., Hieu, N.T., Schmidt, B.: CBESW: sequence alignment on Playstation 3. BMC Bioinform. 9, 377 (2008)","journal-title":"BMC Bioinform."},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1186\/1756-0500-1-107","volume":"1","author":"A Szalkowski","year":"2008","unstructured":"Szalkowski, A., Ledergerber, C., Krahenbuhl, P., Dessimoz, C.: SWPS3 fast multi-threaded vectorized Smith-Waterman for IBM Cell\/B.E. and x86\/SSE2. BMC Res. Notes 1, 107 (2008)","journal-title":"BMC Res. Notes"},{"key":"23_CR22","doi-asserted-by":"publisher","first-page":"1270","DOI":"10.1109\/TPDS.2007.1069","volume":"18","author":"W Liu","year":"2007","unstructured":"Liu, W., Schmidt, B., Voss, G., Muller-Wittig, W.: Streaming algorithms for biological sequence alignment on GPUs. IEEE Trans. Parallel Distrib. Syst. 18, 1270\u20131281 (2007)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"S10","DOI":"10.1186\/1471-2105-9-S2-S10","volume":"9","author":"SA Manavski","year":"2008","unstructured":"Manavski, S.A., Valle, G.: CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinform. 9, S10 (2008)","journal-title":"BMC Bioinform."},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"Ligowski, L., Rudnicki, W.: An efficient implementation of Smith Waterman algorithm on GPU using CUDA, for massively parallel scanning of sequence databases. In: 2009 IEEE International Symposium on Parallel and Distributed Processing, pp. 1\u20138 (2009)","DOI":"10.1109\/IPDPS.2009.5160931"},{"key":"23_CR25","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1186\/1756-0500-3-93","volume":"3","author":"Y Liu","year":"2010","unstructured":"Liu, Y., Schmidt, B., Maskel, D.L.: CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions. BMC Res. Notes 3, 93 (2010)","journal-title":"BMC Res. Notes"},{"key":"23_CR26","doi-asserted-by":"publisher","first-page":"4247","DOI":"10.1016\/j.jcp.2010.02.009","volume":"229","author":"A Khajeh-Saeed","year":"2010","unstructured":"Khajeh-Saeed, A., Poole, S., Perot, J.: Acceleration of the Smith Waterman algorithm using single and multiple graphics processors. J. Comput. Phys. 229, 4247\u20134258 (2010)","journal-title":"J. Comput. Phys."},{"key":"23_CR27","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 Bioinform. 12, 181 (2011)","journal-title":"BMC Bioinform."},{"key":"23_CR28","doi-asserted-by":"crossref","unstructured":"Hains, D., Cashero, Z., Ottenberg, M., Bohm, W., Rajopadhye, S.: Improving CUDASW++, a parallelization of Smith-Waterman for CUDA enabled devices. In: 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, pp. 490\u2013501 (2011)","DOI":"10.1109\/IPDPS.2011.182"},{"issue":"5","key":"23_CR29","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1109\/TPDS.2012.194","volume":"24","author":"EF de Oliveira Sandes","year":"2013","unstructured":"de Oliveira Sandes, E.F., de Melo, A.C.M.: Retrieving Smith-Waterman alignments with optimizations for megabase biological sequences using GPU. IEEE Trans. Parallel Distrib. Syst. 24(5), 1009\u20131021 (2013)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"23_CR30","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. 14, 117 (2013)","journal-title":"BMC Bioinform."},{"key":"23_CR31","unstructured":"Liu, Y., Schmidt, B., Maskell, D.L.: MSA-CUDA: multiple sequence alignment on graphics processing units with CUDA. In: 20th IEEE International Conference on Application-Specific Systems, Architectures and Processors (2009)"},{"key":"23_CR32","first-page":"11","volume":"4","author":"EW Myers","year":"1988","unstructured":"Myers, E.W., Miller, W.: Optimal alignments in linear space. Comput. Appl. Biosci. 4, 11\u201317 (1988)","journal-title":"Comput. Appl. Biosci."},{"key":"23_CR33","unstructured":"Darling, A., Carey, L., Feng, W.: The design, implementation, and evaluation of mpiBLAST. In: 4th International Conference on Linux Clusters: The HPC Revolution 2003 in Conjunction with ClusterWorld Conference and Expo (2003)"},{"key":"23_CR34","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1093\/bioinformatics\/btt013","volume":"29","author":"CS Oehmen","year":"2013","unstructured":"Oehmen, C.S., Baxter, J.: ScalaBLAST 2.0: rapid and robust BLAST calculations on multiprocessor systems. Bioinformatics 29, 797\u2013798 (2013)","journal-title":"Bioinformatics"},{"key":"23_CR35","doi-asserted-by":"publisher","first-page":"1923","DOI":"10.1109\/TPDS.2012.19","volume":"23","author":"C Wu","year":"2012","unstructured":"Wu, C., Kalyanaraman, A., Cannon, W.R.: pGraph: efficient parallel construction of large-scale protein sequence homology graphs. IEEE Trans. Parallel Distrib. Syst. 23, 1923\u20131933 (2012)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"23_CR36","doi-asserted-by":"publisher","first-page":"10915","DOI":"10.1073\/pnas.89.22.10915","volume":"89","author":"S Henikoff","year":"1992","unstructured":"Henikoff, S., Henikoff, J.: Amino acid substitution matrices from protein blocks. PNAS 89, 10915\u201310919 (1992)","journal-title":"PNAS"},{"key":"23_CR37","first-page":"345","volume-title":"Atlas of Protein Sequence and Structure","author":"M Dayhoff","year":"1978","unstructured":"Dayhoff, M., Schwartz, R., Orcutt, B.: A model of evolutionary change in proteins. In: Dayhoff, M.O. (ed.) Atlas of Protein Sequence and Structure, vol. 5, pp. 345\u2013358. National Biomedical Research Foundation, Washington DC (1978)"},{"key":"23_CR38","doi-asserted-by":"publisher","first-page":"3955","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 28, 3955 (2008)","journal-title":"IEEE Micro"},{"key":"23_CR39","unstructured":"NVIDIA: NVIDIAs Next Generation CUDA Compute Architecture: Fermi. NVIDIA Corporation Whitepaper (2009)"},{"key":"23_CR40","unstructured":"NVIDIA: NVIDIAs Next Generation CUDA Compute Architecture: Kepler GK110. NVIDIA Corporation Whitepaper (2012)"},{"key":"23_CR41","doi-asserted-by":"publisher","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","volume":"25","author":"H Li","year":"2009","unstructured":"Li, H., Handsaker, B., Wysoker, A., Fennell, T., Ruan, J., Homer, N., Marth, G., Abecasis, G., Durbin, R.: 1000 genome project data processing subgroup: the sequence alignment\/map format and SAMtools. Bioinformatics 25, 2078\u20132079 (2009)","journal-title":"Bioinformatics"},{"key":"23_CR42","unstructured":"Liu, Y., Schmidt, B., Maskell, D.L.: Parallel reconstruction of neighbor-joining trees for large multiple sequence alignments using CUDA. In: IEEE International Symposium on Parallel and Distributed Processing (2009)"},{"key":"23_CR43","doi-asserted-by":"publisher","first-page":"2534","DOI":"10.1093\/bioinformatics\/btq485","volume":"26","author":"G Rizk","year":"2010","unstructured":"Rizk, G., Lavenier, D.: GASSST: global alignment short sequence search tool. Bioinformatics 26, 2534\u20132540 (2010)","journal-title":"Bioinformatics"},{"key":"23_CR44","doi-asserted-by":"publisher","first-page":"i318","DOI":"10.1093\/bioinformatics\/bts414","volume":"28","author":"Y Liu","year":"2012","unstructured":"Liu, Y., Schmidt, B.: Long read alignment based on maximal exact match seeds. Bioinformatics 28, i318\u2013i324 (2012)","journal-title":"Bioinformatics"},{"key":"23_CR45","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 9, 357\u2013359 (2012)","journal-title":"Nat. Methods"}],"container-title":["Lecture Notes in Computer Science","Parallel Processing and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-55195-6_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,30]],"date-time":"2023-01-30T22:37:00Z","timestamp":1675118220000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-55195-6_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642551949","9783642551956"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-55195-6_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 May 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}