{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T07:38:46Z","timestamp":1769067526278,"version":"3.49.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/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]]},"DOI":"10.1186\/s12859-019-2827-0","type":"journal-article","created":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T10:11:46Z","timestamp":1558433506000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Pairwise alignment of nucleotide sequences using maximal exact matches"],"prefix":"10.1186","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8799-7776","authenticated-orcid":false,"given":"Arash","family":"Bayat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Ga\u00ebta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksandar","family":"Ignjatovic","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sri","family":"Parameswaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,21]]},"reference":[{"key":"2827_CR1","doi-asserted-by":"crossref","DOI":"10.1525\/9780520943742","volume-title":"Sequence alignment: methods, models, concepts, and strategies","author":"MS Rosenberg","year":"2009","unstructured":"Rosenberg MS. Sequence alignment: methods, models, concepts, and strategies. London: University of California Press; 2009."},{"issue":"14","key":"2827_CR2","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H Li","year":"2009","unstructured":"Li H, Durbin R. Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics (Oxford, England). 2009; 25(14):1754\u201360.","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2827_CR3","unstructured":"Li H. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. 2013:. p. 3. https:\/\/arxiv.org\/abs\/1303.3997 ."},{"issue":"3","key":"2827_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead B, Trapnell C, Pop M, Salzberg SL. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 2009; 10(3):25.","journal-title":"Genome Biol"},{"issue":"4","key":"2827_CR5","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead B, Salzberg SL. Fast gapped-read alignment with Bowtie 2. Nat Methods. 2012; 9(4):357\u20139.","journal-title":"Nat Methods"},{"issue":"3","key":"2827_CR6","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.","journal-title":"J Mol Biol"},{"issue":"4","key":"2827_CR7","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1101\/gr.229202","volume":"12","author":"WJ Kent","year":"2002","unstructured":"Kent WJ. Blat\u2014the blast-like alignment tool. Genome Res. 2002; 12(4):656\u201364.","journal-title":"Genome Res"},{"issue":"2","key":"2827_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1186\/gb-2004-5-2-r12","volume":"5","author":"S Kurtz","year":"2004","unstructured":"Kurtz S, Phillippy A, Delcher AL, Smoot M, Shumway M, Antonescu C, Salzberg SL. Versatile and open software for comparing large genomes. Genome Biol. 2004; 5(2):12.","journal-title":"Genome Biol"},{"issue":"3","key":"2827_CR9","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","volume":"18","author":"B Ma","year":"2002","unstructured":"Ma B, Tromp J, Li M. Patternhunter: faster and more sensitive homology search. Bioinformatics. 2002; 18(3):440\u20135.","journal-title":"Bioinformatics"},{"issue":"03","key":"2827_CR10","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1142\/S0219720004000661","volume":"2","author":"M Li","year":"2004","unstructured":"Li M, Ma B, Kisman D, Tromp J. Patternhunter ii: Highly sensitive and fast homology search. J Bioinforma Comput Biol. 2004; 2(03):417\u201339.","journal-title":"J Bioinforma Comput Biol"},{"issue":"1-2","key":"2827_CR11","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0020-0255(01)00098-6","volume":"135","author":"P Ferragina","year":"2001","unstructured":"Ferragina P, Manzini G. An experimental study of a compressed index. Inf Sci. 2001; 135(1-2):13\u201328.","journal-title":"Inf Sci"},{"key":"2827_CR12","unstructured":"Zaharia M, Bolosky WJ, Curtis K, Fox A, Patterson D, Shenker S, Stoica I, Karp RM, Sittler T. Faster and More Accurate Sequence Alignment with SNAP. 2011. arXiv."},{"issue":"12","key":"2827_CR13","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1038\/nmeth.2221","volume":"9","author":"S Marco-Sola","year":"2012","unstructured":"Marco-Sola S, Sammeth M, Guig\u00f3 R, Ribeca P. The GEM mapper: fast, accurate and versatile alignment by filtration. Nat Methods. 2012; 9(12):1185\u20138.","journal-title":"Nat Methods"},{"issue":"3","key":"2827_CR14","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0166-218X(03)00382-2","volume":"138","author":"U Keich","year":"2004","unstructured":"Keich U, Li M, Ma B, Tromp J. On spaced seeds for similarity search. Discret Appl Math. 2004; 138(3):253\u201363.","journal-title":"Discret Appl Math"},{"issue":"3","key":"2827_CR15","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"},{"issue":"1","key":"2827_CR16","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":"1-3","key":"2827_CR17","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P Bille","year":"2005","unstructured":"Bille P. A survey on tree edit distance and related problems. Theor Comput Sci. 2005; 337(1-3):217\u201339.","journal-title":"Theor Comput Sci"},{"issue":"3","key":"2827_CR18","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":"1","key":"2827_CR19","doi-asserted-by":"publisher","first-page":"86869","DOI":"10.1371\/journal.pone.0086869","volume":"9","author":"Y Liu","year":"2014","unstructured":"Liu Y, Popp B, Schmidt B. CUSHAW3: sensitive and accurate base-space and color-space short-read alignment with hybrid seeding. PLoS ONE. 2014; 9(1):86869.","journal-title":"PLoS ONE"},{"issue":"2","key":"2827_CR20","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"},{"key":"2827_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, Kr\u00e4henb\u00fchl P, Dessimoz C. SWPS3 - fast multi-threaded vectorized Smith-Waterman for IBM Cell\/B.E. and x86\/SSE2. BMC Res Notes. 2008; 1:107.","journal-title":"BMC Res Notes"},{"issue":"12","key":"2827_CR22","doi-asserted-by":"publisher","first-page":"82138","DOI":"10.1371\/journal.pone.0082138","volume":"8","author":"M Zhao","year":"2013","unstructured":"Zhao M, Lee ea. SSW Library: An SIMD Smith-Waterman C\/C++ Library for Use in Genomic Applications. PLoS ONE. 2013; 8(12):82138.","journal-title":"PLoS ONE"},{"issue":"1","key":"2827_CR23","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1186\/1471-2105-9-11","volume":"9","author":"A D\u00f6ring","year":"2008","unstructured":"D\u00f6ring A, Weese ea. SeqAn An efficient, generic C++ library for sequence analysis. BMC Bioinformatics. 2008; 9(1):11.","journal-title":"BMC Bioinformatics"},{"issue":"3","key":"2827_CR24","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/316542.316550","volume":"46","author":"G Myers","year":"1999","unstructured":"Myers G. A fast bit-vector algorithm for approximate string matching based on dynamic programming. J ACM. 1999; 46(3):395\u2013415.","journal-title":"J ACM"},{"issue":"1","key":"2827_CR25","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):100\u201318.","journal-title":"Inf Control"},{"issue":"1-2","key":"2827_CR26","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1089\/10665270050081478","volume":"7","author":"Z Zhang","year":"2000","unstructured":"Zhang Z, Schwartz S, Wagner L, Miller W. A greedy algorithm for aligning dna sequences. J Comput Biol. 2000; 7(1-2):203\u201314.","journal-title":"J Comput Biol"},{"key":"2827_CR27","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:117.","journal-title":"BMC Bioinformatics"},{"key":"2827_CR28","doi-asserted-by":"publisher","unstructured":"Harris B, Jacob AC, Lancaster JM, Buhler J, Chamberlain RD. A Banded Smith-Waterman FPGA Accelerator for Mercury BLASTP. In: 2007 International Conference on Field Programmable Logic and Applications. IEEE: 2007. p. 765\u20139. https:\/\/doi.org\/10.1109\/FPL.2007.4380764 .","DOI":"10.1109\/FPL.2007.4380764"},{"key":"2827_CR29","doi-asserted-by":"publisher","unstructured":"Allred J, Coyne J, Lynch W, Natoli V, Grecco J, Morrissette J. Smith-Waterman implementation on a FSB-FPGA module using the Intel Accelerator Abstraction Layer. In: 2009 IEEE International Symposium on Parallel & Distributed Processing. IEEE: 2009. p. 1\u20134. https:\/\/doi.org\/10.1109\/IPDPS.2009.5161214 .","DOI":"10.1109\/IPDPS.2009.5161214"},{"issue":"5","key":"2827_CR30","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1038\/ng.806","volume":"43","author":"MA DePristo","year":"2011","unstructured":"DePristo MA, Banks ea. A framework for variation discovery and genotyping using next-generation DNA sequencing data. Nat Genet. 2011; 43(5):491\u20138.","journal-title":"Nat Genet"},{"issue":"8","key":"2827_CR31","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1038\/ng.3036","volume":"46","author":"A Rimmer","year":"2014","unstructured":"Rimmer A, Phan H, Mathieson I, Iqbal Z, Twigg SRF, Wilkie AOM, McVean G, Lunter G, WGS500 Consortium and others. Integrating mapping-, assembly-and haplotype-based approaches for calling variants in clinical sequencing applications. Nat Genet. 2014; 46(8):912.","journal-title":"Nat Genet"},{"issue":"13","key":"2827_CR32","doi-asserted-by":"publisher","first-page":"1609","DOI":"10.1093\/bioinformatics\/btp275","volume":"25","author":"Z Khan","year":"2009","unstructured":"Khan Z, Bloom JS, Kruglyak L, Singh M. A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays. Bioinformatics. 2009; 25(13):1609\u201316.","journal-title":"Bioinformatics"},{"key":"2827_CR33","unstructured":"Aluru S. Handbook of computational molecular biology.Chapman & All\/Crc Computer and Information Science Series; 2005."},{"issue":"5","key":"2827_CR34","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1093\/bioinformatics\/8.5.481","volume":"8","author":"K-M Chao","year":"1992","unstructured":"Chao K-M, Pearson WR, Miller W. Aligning two sequences within a specified diagonal band. Bioinformatics. 1992; 8(5):481\u20137.","journal-title":"Bioinformatics"},{"issue":"7571","key":"2827_CR35","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1038\/nature15393","volume":"526","author":"Richard A. Gibbs","year":"2015","unstructured":"1000 Genomes Project Consortium. A global reference for human genetic variation. Nature. 2015; 526(7571):68\u201374. https:\/\/doi.org\/10.1038\/nature15393 .","journal-title":"Nature"},{"issue":"10","key":"2827_CR36","doi-asserted-by":"publisher","first-page":"1553","DOI":"10.1093\/bioinformatics\/btu856","volume":"31","author":"H Xin","year":"2015","unstructured":"Xin H, Greth J, Emmons J, Pekhimenko G, Kingsford C, Alkan C, Mutlu O. Shifted Hamming distance: a fast and accurate SIMD-friendly filter to accelerate alignment verification in read mapping. Bioinformatics (Oxford, England). 2015; 31(10):1553\u201360.","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2827_CR37","unstructured":"Alser M, Hassan H, Xin H, Ergin O, Mutlu O, Alkan C. GateKeeper : Enabling Fast Pre-Alignment in DNA Short Read Mapping with a New Streaming Accelerator Architecture. 2016. http:\/\/arxiv.org\/abs\/1604.01789."},{"issue":"7","key":"2827_CR38","doi-asserted-by":"publisher","first-page":"1002195","DOI":"10.1371\/journal.pbio.1002195","volume":"13","author":"ZD Stephens","year":"2015","unstructured":"Stephens ZD, Lee SY, Faghri F, Campbell RH, Zhai C, Efron MJ, Iyer R, Schatz MC, Sinha S, Robinson GE. Big data: astronomical or genomical?. PLoS Biol. 2015; 13(7):1002195.","journal-title":"PLoS Biol"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-2827-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-019-2827-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-2827-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T21:38:51Z","timestamp":1607895531000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-019-2827-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,21]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["2827"],"URL":"https:\/\/doi.org\/10.1186\/s12859-019-2827-0","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,21]]},"assertion":[{"value":"2 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2019","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"}},{"value":"Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Publisher\u2019s Note"}}],"article-number":"261"}}