{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,9]],"date-time":"2026-11-09T22:14:21Z","timestamp":1794262461866,"version":"4.9.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,2,10]],"date-time":"2016-02-10T00:00:00Z","timestamp":1455062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2016,2,10]],"date-time":"2016-02-10T00:00:00Z","timestamp":1455062400000},"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"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Sequence alignment algorithms are a key component of many bioinformatics applications.<\/jats:p>\n                <jats:p>Though various fast Smith-Waterman local sequence alignment implementations have been developed for x86 CPUs, most are embedded into larger database search tools. In addition, fast implementations of Needleman-Wunsch global sequence alignment and its semi-global variants are not as widespread. This article presents the first software library for local, global, and semi-global pairwise intra-sequence alignments and improves the performance of previous intra-sequence implementations.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>A faster intra-sequence local pairwise alignment implementation is described and benchmarked, including new global and semi-global variants. Using a 375 residue query sequence a speed of 136 billion cell updates per second (GCUPS) was achieved on a dual Intel Xeon E5-2670 24-core processor system, the highest reported for an implementation based on Farrar\u2019s \u2018striped\u2019 approach. Rognes\u2019s SWIPE optimal database search application is still generally the fastest available at 1.2 to at best 2.4 times faster than Parasail for sequences shorter than 500 amino acids. However, Parasail was faster for longer sequences. For global alignments, Parasail\u2019s prefix scan implementation is generally the fastest, faster even than Farrar\u2019s \u2018striped\u2019 approach, however the opal library is faster for single-threaded applications. The software library is designed for 64 bit Linux, OS X, or Windows on processors with SSE2, SSE41, or AVX2. Source code is available from <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/jeffdaily\/parasail\">https:\/\/github.com\/jeffdaily\/parasail<\/jats:ext-link>\nunder the Battelle BSD-style license.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>Applications that require optimal alignment scores could benefit from the improved performance. For the first time, SIMD global, semi-global, and local alignments are available in a stand-alone C library.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-016-0930-z","type":"journal-article","created":{"date-parts":[[2016,2,10]],"date-time":"2016-02-10T03:58:01Z","timestamp":1455076681000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":265,"title":["Parasail: SIMD C library for global, semi-global, and local pairwise sequence alignments"],"prefix":"10.1186","volume":"17","author":[{"given":"Jeff","family":"Daily","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,2,10]]},"reference":[{"issue":"22","key":"930_CR1","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 JG. Amino acid substitution matrices from protein blocks. Proc Nat Acad Sci. 1992; 89(22):10915\u20139.","journal-title":"Proc Nat Acad Sci"},{"issue":"1","key":"930_CR2","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/S1046-2023(05)80165-3","volume":"3","author":"DJ States","year":"1991","unstructured":"States DJ, Gish W, Altschul SF. Improved sensitivity of nucleic acid database searches using application-specific scoring matrices. Methods. 1991; 3(1):66\u201370. doi:10.1016\/S1046-2023(05)80165-3.","journal-title":"Methods"},{"issue":"3","key":"930_CR3","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. doi:10.1016\/0022-2836(82)90398-9.","journal-title":"J Mol Biol"},{"issue":"3","key":"930_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 SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool. J Mol Biol. 1990; 215(3):403\u201310. doi:10.1016\/S0022-2836(05)80360-2.","journal-title":"J Mol Biol"},{"issue":"2","key":"930_CR5","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 CABIOS. 1997; 13(2):145\u201350. doi:10.1093\/bioinformatics\/13.2.145.","journal-title":"Comput Appl Biosci CABIOS"},{"issue":"8","key":"930_CR6","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. doi:10.1093\/bioinformatics\/16.8.699.","journal-title":"Bioinformatics"},{"issue":"2","key":"930_CR7","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. doi:10.1093\/bioinformatics\/btl582.","journal-title":"Bioinformatics"},{"issue":"1","key":"930_CR8","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":"12","key":"930_CR9","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(12):82138. doi:10.1371\/journal.pone.0082138.","journal-title":"PLoS ONE"},{"key":"930_CR10","volume-title":"Application-specific Systems, Architectures and Processors (ASAP), 2014 IEEE 25th International Conference On","author":"Y Liu","year":"2014","unstructured":"Liu Y, Schmidt B. Swaphi: Smith-waterman protein database search on xeon phi coprocessors. In: Application-specific Systems, Architectures and Processors (ASAP), 2014 IEEE 25th International Conference On: 2014. p. 184\u20135. doi:10.1109\/ASAP.2014.6868657."},{"key":"930_CR11","volume-title":"Parallel and Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International","author":"L Wang","year":"2014","unstructured":"Wang L, Chan Y, Duan X, Lan H, Meng X, Liu W. Xsw: Accelerating biological database search on xeon phi. In: Parallel and Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International: 2014. p. 950\u20137. doi:10.1109\/IPDPSW.2014.108."},{"key":"930_CR12","doi-asserted-by":"crossref","unstructured":"Daily J. Scalable parallel methods for analyzing metagenomics data at extreme scale: Thesis, Washington State University; 2015. https:\/\/research.wsulibs.wsu.edu\/xmlui\/handle\/2376\/5503. Accessed 9 Oct 2015.","DOI":"10.2172\/1186981"},{"issue":"0","key":"930_CR13","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.jpdc.2014.08.009","volume":"79\u201380","author":"J Daily","year":"2015","unstructured":"Daily J, Kalyanaraman A, Krishnamoorthy S, Vishnu A. A work stealing based approach for enabling scalable optimal sequence homology detection. J Parallel Distributed Comput. 2015; 79\u201380(0):132\u201342. doi:10.1016\/j.jpdc.2014.08.009.","journal-title":"J Parallel Distributed Comput"},{"key":"930_CR14","unstructured":"\u0160o\u0161ic M. An simd dynamic programming c\/c++ library: Thesis, University of Zagreb; 2015. https:\/\/bib.irb.hr\/datoteka\/758607.diplomski_Martin_Sosic.pdf."},{"key":"930_CR15","unstructured":"Frielingsdorf JT. Improving optimal sequence alignments through a simd-accelerated library: Thesis, University of Oslo; 2015. http:\/\/urn.nb.no\/URN:NBN:no-49935. Accessed 10 Dec 2015."},{"issue":"1","key":"930_CR16","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. 2008; 1(1):107.","journal-title":"BMC Res Notes"},{"key":"930_CR17","doi-asserted-by":"publisher","DOI":"10.1201\/9781420036275.ch7","volume-title":"Enhanced Suffix Arrays and Applications","author":"MI Abouelhoda","year":"2005","unstructured":"Abouelhoda MI, Kurtz S, Ohlebusch E. 7. In: Aluru S, editor. Enhanced Suffix Arrays and Applications. Boca Raton, FL: Chapman & Hall\/CRC: 2005. p. 27."},{"key":"930_CR18","volume-title":"Proceedings of the 12th international conference on Algorithms and data structures (WADS\u201911)","author":"J Fischer","year":"2011","unstructured":"Fischer J. Inducing the LCP-array In: Dehne F, Iacono J, Sack J-R, editors. Proceedings of the 12th international conference on Algorithms and data structures (WADS\u201911). Berlin, Heidelberg: Springer-Verlag: 2011. p. 374\u201385."},{"key":"930_CR19","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1186\/1471-2105-10-421","volume":"10","author":"C Camacho","year":"2009","unstructured":"Camacho C, Coulouris G, Avagyan V, Ma N, Papadopoulos J, Bealer K, Madden TL. Blast+: architecture and applications. BMC Bioinformatics. 2009; 10:421\u20131. doi:10.1186\/1471-2105-10-421.","journal-title":"BMC Bioinformatics"},{"key":"930_CR20","unstructured":"Hyper-Threading. Website. https:\/\/www.nersc.gov\/users\/computational-systems\/edison\/performance-and-optimization\/hyper-threading\/. Accessed: 2015-11-17."},{"issue":"D1","key":"930_CR21","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1093\/nar\/gku989","volume":"43","author":"The UniProt Consortium","year":"2015","unstructured":"The UniProt Consortium. Uniprot: A hub for protein information. Nucleic Acids Res. 2015; 43(D1):204\u201312. doi:10.1093\/nar\/gku989.","journal-title":"Nucleic Acids Res"},{"key":"930_CR22","unstructured":"Protein BLAST: search protein databases using a protein query. Website. http:\/\/blast.ncbi.nlm.nih.gov\/Blast.cgi?PAGE=Proteins, Accessed: 2015-11-17."},{"key":"930_CR23","unstructured":"scikit-bio. Website. http:\/\/scikit-bio.org\/, Accessed: 2015-11-06."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-016-0930-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-016-0930-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-016-0930-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-016-0930-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T17:59:25Z","timestamp":1706810365000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-016-0930-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,10]]},"references-count":23,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["930"],"URL":"https:\/\/doi.org\/10.1186\/s12859-016-0930-z","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,10]]},"assertion":[{"value":"18 November 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"81"}}