{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T04:54:30Z","timestamp":1782363270182,"version":"3.54.5"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,3,9]],"date-time":"2018-03-09T00:00:00Z","timestamp":1520553600000},"content-version":"tdm","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":[[2018,12]]},"DOI":"10.1186\/s12859-018-2094-5","type":"journal-article","created":{"date-parts":[[2018,3,9]],"date-time":"2018-03-09T08:02:48Z","timestamp":1520582568000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Fast and efficient short read mapping based on a succinct hash index"],"prefix":"10.1186","volume":"19","author":[{"given":"Haowen","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuandong","family":"Chan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kaichao","family":"Fan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bertil","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weiguo","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,3,9]]},"reference":[{"issue":"1","key":"2094_CR1","doi-asserted-by":"publisher","first-page":"S13","DOI":"10.1186\/1471-2164-14-13","volume":"14","author":"H Xin","year":"2013","unstructured":"Xin H, Lee D, Hormozdiari F, et al.Accelerating read mapping with FastHASH[J]. BMC Genomics. 2013; 14(1):S13.","journal-title":"BMC Genomics"},{"issue":"8","key":"2094_CR2","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1038\/nmeth0810-576","volume":"7","author":"F Hach","year":"2010","unstructured":"Hach F, Hormozdiari F, Alkan C, et al.mrsFAST: a cache-oblivious algorithm for short-read mapping[J]. Nat Methods. 2010; 7(8):576\u201377.","journal-title":"Nat Methods"},{"issue":"20","key":"2094_CR3","doi-asserted-by":"publisher","first-page":"2592","DOI":"10.1093\/bioinformatics\/bts505","volume":"28","author":"D Weese","year":"2012","unstructured":"Weese D, Holtgrewe M, Reinert K. RazerS 3: faster, fully sensitive read mapping[J]. Bioinformatics. 2012; 28(20):2592\u20139.","journal-title":"Bioinformatics"},{"issue":"1","key":"2094_CR4","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1186\/s12859-015-0626-9","volume":"16","author":"H Cheng","year":"2015","unstructured":"Cheng H, Jiang H, Yang J, et al.BitMapper: an efficient all-mapper based on bit-vector computing[J]. BMC Bioinforma. 2015; 16(1):192.","journal-title":"BMC Bioinforma"},{"issue":"6","key":"2094_CR5","doi-asserted-by":"publisher","first-page":"e41","DOI":"10.1093\/nar\/gkr1246","volume":"40","author":"A Ahmadi","year":"2011","unstructured":"Ahmadi A, Behm A, Honnalli N, et al.Hobbes: optimized gram-based methods for efficient read alignment[J]. Nucleic Acids Res. 2011; 40(6):e41.","journal-title":"Nucleic Acids Res"},{"issue":"3","key":"2094_CR6","doi-asserted-by":"publisher","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead B, Trapnell C, Pop M, et al.Ultrafast and memory-efficient alignment of short DNA sequences to the human genome[J]. Genome Biol. 2009; 10(3):R25.","journal-title":"Genome Biol"},{"issue":"14","key":"2094_CR7","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[J]. Bioinformatics. 2009; 25(14):1754\u201360.","journal-title":"Bioinformatics"},{"issue":"12","key":"2094_CR8","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, et al.The GEM mapper: fast, accurate and versatile alignment by filtration[J]. Nat Methods. 2012; 9(12):1185\u20138.","journal-title":"Nat Methods"},{"issue":"11","key":"2094_CR9","doi-asserted-by":"publisher","first-page":"1495","DOI":"10.1089\/cmb.2011.0185","volume":"18","author":"D Newkirk","year":"2011","unstructured":"Newkirk D, Biesinger J, Chon A, et al.AREM: aligning short reads from ChIP-sequencing by expectation maximization[J]. J Comput Biol. 2011; 18(11):1495\u2013505.","journal-title":"J Comput Biol"},{"issue":"1","key":"2094_CR10","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1038\/nmeth.2251","volume":"10","author":"A Roberts","year":"2013","unstructured":"Roberts A, Pachter L. Streaming fragment assignment for real-time analysis of sequencing experiments[J]. Nat Methods. 2013; 10(1):71\u20133.","journal-title":"Nat Methods"},{"issue":"3","key":"2094_CR11","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]. J Mol Biol. 1970; 48(3):443\u201353.","journal-title":"J Mol Biol"},{"issue":"1","key":"2094_CR12","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]. J Mol Biol. 1981; 147(1):195\u20137.","journal-title":"J Mol Biol"},{"key":"2094_CR13","volume-title":"IEEE Conference Record of 14th Annual Symposium on","author":"P Weiner","year":"1973","unstructured":"Weiner P. Linear pattern matching algorithms[C]\/\/Switching and Automata Theory, 1973. SWAT\u201973. In: IEEE Conference Record of 14th Annual Symposium on. Washington DC: IEEE: 1973. p. 1\u201311."},{"issue":"5","key":"2094_CR14","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers G. Suffix arrays: a new method for on-line string searches[J]. Siam J Comput. 1993; 22(5):935\u201348.","journal-title":"Siam J Comput"},{"key":"2094_CR15","volume-title":"A block-sorting lossless data compression algorithm[J], Technical Report 124,","author":"M Burrows","year":"1994","unstructured":"Burrows M, Wheeler DJ. A block-sorting lossless data compression algorithm[J], Technical Report 124,Palo Alto: DEC Digital Systems Research Center; 1994."},{"issue":"2","key":"2094_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.19153\/1.2.1","volume":"1","author":"G Navarro","year":"1998","unstructured":"Navarro G, Baeza-Yates R. A practical q-gram index for text retrieval allowing errors[J]. CLEI Electronic J. 1998; 1(2):1.","journal-title":"CLEI Electronic J"},{"key":"2094_CR17","volume-title":"Annual Symposium on Combinatorial Pattern Matching","author":"G Navarro","year":"2000","unstructured":"Navarro G, Sutinen E, Tanninen J, et al.Indexing text with approximate q-grams[C]. In: Annual Symposium on Combinatorial Pattern Matching. Berlin, Heidelberg: Springer: 2000. p. 350\u201363."},{"key":"2094_CR18","volume-title":"Proceedings of the third annual international conference on Computational molecular biology","author":"S Burkhardt","year":"1999","unstructured":"Burkhardt S, Crauser A, Ferragina P, et al.q-gram based database searching using a suffix array (QUASAR)[C]. In: Proceedings of the third annual international conference on Computational molecular biology. Pittsburgh: ACM: 1999. p. 77\u201383."},{"key":"2094_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1146\/annurev-genom-090413-025358","volume":"16","author":"K Reinert","year":"2015","unstructured":"Reinert K, Langmead B, Weese D, et al.Alignment of next-generation sequencing reads[J]. Annu Rev Genomics Hum Genet. 2015; 16:133\u201351.","journal-title":"Annu Rev Genomics Hum Genet"},{"issue":"11","key":"2094_CR20","doi-asserted-by":"publisher","first-page":"1632","DOI":"10.1093\/bioinformatics\/btv670","volume":"32","author":"H Xin","year":"2015","unstructured":"Xin H, Nahar S, Zhu R, et al.Optimal seed solver: optimizing seed selection in read mapping[J]. Bioinformatics. 2015; 32(11):1632\u201342.","journal-title":"Bioinformatics"},{"issue":"3","key":"2094_CR21","doi-asserted-by":"publisher","first-page":"3487","DOI":"10.1101\/gr.113985.110","volume":"21","author":"SM Kielbasa","year":"2011","unstructured":"Kielbasa SM, et al.Adaptive seeds tame genomic sequence comparison. Genome Res. 2011; 21(3):3487\u201393.","journal-title":"Genome Res"},{"issue":"3","key":"2094_CR22","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]. J ACM (JACM). 1999; 46(3):395\u2013415.","journal-title":"J ACM (JACM)"},{"key":"2094_CR23","unstructured":"Cheng H, et al. \n                    http:\/\/home.ustc.edu.cn~chhy\/BitMapper2.html\n                    \n                  . Accessed 2 Aug 2017."},{"issue":"1","key":"2094_CR24","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1186\/1471-2105-15-42","volume":"15","author":"J Kim","year":"2014","unstructured":"Kim J, Li C, Xie X. Improving read mapping using additional prefix grams[J]. BMC Bioinforma. 2014; 15(1):42.","journal-title":"BMC Bioinforma"},{"issue":"7","key":"2094_CR25","doi-asserted-by":"publisher","first-page":"e78","DOI":"10.1093\/nar\/gkt005","volume":"41","author":"E Siragusa","year":"2013","unstructured":"Siragusa E, Weese D, Reinert K. Fast and accurate read mapping with approximate seeds and multiple backtracking[J]. Nucleic Acids Res. 2013; 41(7):e78.","journal-title":"Nucleic Acids Res"},{"key":"2094_CR26","volume-title":"Data Engineering (ICDE), 2016 IEEE 32nd International Conference on","author":"J Kim","year":"2016","unstructured":"Kim J, Li C, Xie X. Hobbes3: Dynamic generation of variable-length signatures for efficient approximate subsequence mappings[C]. In: Data Engineering (ICDE), 2016 IEEE 32nd International Conference on. Washington DC: IEEE: 2016. p. 169\u201380."},{"key":"2094_CR27","unstructured":"Holtgrewe M. Mason-a read simulator for second generation sequencing data[J]. 2010. Technical Report FU Berlin. Mathematics Department, TR-B-10-06."},{"issue":"1","key":"2094_CR28","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1186\/1471-2105-12-210","volume":"12","author":"M Holtgrewe","year":"2011","unstructured":"Holtgrewe M, Emde AK, Weese D, et al.A novel and well-defined benchmarking method for second generation read mapping[J]. BMC Bioinforma. 2011; 12(1):210.","journal-title":"BMC Bioinforma"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-018-2094-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-018-2094-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-018-2094-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T19:08:57Z","timestamp":1552072137000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-018-2094-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,9]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["2094"],"URL":"https:\/\/doi.org\/10.1186\/s12859-018-2094-5","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,9]]},"assertion":[{"value":"1 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2018","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":"92"}}