{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T15:38:01Z","timestamp":1772725081244,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"S1","license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Genomics"],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>With the introduction of next-generation sequencing (NGS) technologies, we are facing an exponential increase in the amount of genomic sequence data. The success of all medical and genetic applications of next-generation sequencing critically depends on the existence of computational techniques that can process and analyze the enormous amount of sequence data quickly and accurately. Unfortunately, the current read mapping algorithms have difficulties in coping with the massive amounts of data generated by NGS.<\/jats:p>\n          <jats:p>We propose a new algorithm, FastHASH, which drastically improves the performance of the seed-and-extend type hash table based read mapping algorithms, while maintaining the high sensitivity and comprehensiveness of such methods. FastHASH is a generic algorithm compatible with all seed-and-extend class read mapping algorithms. It introduces two main techniques, namely <jats:italic>Adjacency Filtering<\/jats:italic>, and <jats:italic>Cheap K-mer Selection<\/jats:italic>.<\/jats:p>\n          <jats:p>We implemented FastHASH and merged it into the codebase of the popular read mapping program, mrFAST. Depending on the edit distance cutoffs, we observed up to 19-fold speedup while still maintaining 100% sensitivity and high comprehensiveness.<\/jats:p>","DOI":"10.1186\/1471-2164-14-s1-s13","type":"journal-article","created":{"date-parts":[[2019,12,11]],"date-time":"2019-12-11T01:59:19Z","timestamp":1576029559000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":77,"title":["Accelerating read mapping with FastHASH"],"prefix":"10.1186","volume":"14","author":[{"given":"Hongyi","family":"Xin","sequence":"first","affiliation":[]},{"given":"Donghyuk","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Farhad","family":"Hormozdiari","sequence":"additional","affiliation":[]},{"given":"Samihan","family":"Yedkar","sequence":"additional","affiliation":[]},{"given":"Onur","family":"Mutlu","sequence":"additional","affiliation":[]},{"given":"Can","family":"Alkan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,21]]},"reference":[{"issue":"6","key":"4628_CR1","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1038\/76469","volume":"18","author":"S Brenner","year":"2000","unstructured":"Brenner S, Johnson M, Bridgham J, Golda G, Lloyd DH, Johnson D, Luo S, McCurdy S, Foy M, Ewan M, Roth R, George D, Eletr S, Albrecht G, Vermaas E, Williams SR, Moon K, Burcham T, Pallas M, DuBridge RB, Kirchner J, Fearon K, i Mao J, Corcoran K: Gene expression analysis by massively parallel signature sequencing (MPSS) on microbead arrays. Nat Biotechnol. 2000, 18 (6): 630-4. 10.1038\/76469.","journal-title":"Nat Biotechnol"},{"key":"4628_CR2","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1038\/nature09534","volume":"467","author":"1000 Genomes Project Consortium","year":"2010","unstructured":"1000 Genomes Project Consortium: A map of human genome variation from population-scale sequencing. Nature. 2010, 467: 1061-1073. 10.1038\/nature09534.","journal-title":"Nature"},{"key":"4628_CR3","doi-asserted-by":"publisher","first-page":"2555","DOI":"10.1093\/hmg\/ddp187","volume":"18","author":"F Antonacci","year":"2009","unstructured":"Antonacci F, Kidd JM, Marques-Bonet T et al: Characterization of six human disease-associated in-version polymorphisms. Hum Mol Genet. 2009, 18: 2555-2566. 10.1093\/hmg\/ddp187.","journal-title":"Hum Mol Genet"},{"key":"4628_CR4","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1038\/ng.643","volume":"42","author":"F Antonacci","year":"2010","unstructured":"Antonacci F, Kidd JM, Marques-Bonet T et al: A large and complex structural polymorphism at 16p12.1 underlies microdeletion disease risk. Nat Genet. 2010, 42: 745-750. 10.1038\/ng.643.","journal-title":"Nat Genet"},{"key":"4628_CR5","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1038\/nrg1895","volume":"7","author":"JA Bailey","year":"2006","unstructured":"Bailey JA, Eichler EE: Primate segmental duplications: crucibles of evolution, diversity and disease. Nat Rev Genet. 2006, 7: 552-564.","journal-title":"Nat Rev Genet"},{"key":"4628_CR6","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1126\/science.1072047","volume":"297","author":"JA Bailey","year":"2002","unstructured":"Bailey JA, Gu Z, Clark RA, Reinert K, Samonte RV, Schwartz S, Adams MD, Myers EW, Li PW, Eichler EE: Recent segmental duplications in the human genome. Science. 2002, 297: 1003-1007. 10.1126\/science.1072047.","journal-title":"Science"},{"key":"4628_CR7","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1159\/000184713","volume":"123","author":"JA Bailey","year":"2008","unstructured":"Bailey JA, Kidd JM, Eichler EE: Human copy number polymorphic genes. Cytogenet Genome Res. 2008, 123: 234-243. 10.1159\/000184713.","journal-title":"Cytogenet Genome Res"},{"key":"4628_CR8","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1101\/gr.GR-1871R","volume":"11","author":"JA Bailey","year":"2001","unstructured":"Bailey JA, Yavor AM, Massa HF, Trask BJ, Eichler EE: Segmental duplications: organization and impact within the current human genome project assembly. Genome Res. 2001, 11: 1005-1017. 10.1101\/gr.GR-1871R.","journal-title":"Genome Res"},{"key":"4628_CR9","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1086\/338458","volume":"70","author":"JA Bailey","year":"2002","unstructured":"Bailey JA, Yavor AM, Viggiano L, Misceo D, Horvath JE, Archidiacono N, Schwartz S, Rocchi M, Eichler EE: Human-specific duplication and mosaic transcripts: the recent paralogous structure of chromosome 22. Am J Hum Genet. 2002, 70: 83-100. 10.1086\/338458.","journal-title":"Am J Hum Genet"},{"key":"4628_CR10","doi-asserted-by":"publisher","first-page":"R23","DOI":"10.1186\/gb-2004-5-4-r23","volume":"5","author":"JA Bailey","year":"2004","unstructured":"Bailey JA, Baertsch R, Kent WJ, Haussler D, Eichler EE: Hotspots of mammalian chromosomal evolution. Genome Biol. 2004, 5: R23-10.1186\/gb-2004-5-4-r23.","journal-title":"Genome Biol"},{"key":"4628_CR11","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1038\/nature07744","volume":"457","author":"T Marques-Bonet","year":"2009","unstructured":"Marques-Bonet T, Kidd JM, Ventura M, Graves TA, Cheng Z, Hillier LW, Jiang Z, Baker C, Malfavon-Borja R, Fulton LA, Alkan C, Aksay G, Girirajan S, Siswara P, Chen L, Cardone MF, Navarro A, Mardis ER, Wilson RK, Eichler EE: A burst of segmental duplications in the genome of the African great ape ancestor. Nature. 2009, 457: 877-881. 10.1038\/nature07744.","journal-title":"Nature"},{"key":"4628_CR12","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1038\/nature01723","volume":"423","author":"S Rozen","year":"2003","unstructured":"Rozen S, Skaletsky H, Marszalek JD, Minx PJ, Cordum HS, Waterston RH, Wilson RK, Page DC: Abundant gene conversion between arms of palindromes in human and ape Y chromosomes. Nature. 2003, 423: 873-876. 10.1038\/nature01723.","journal-title":"Nature"},{"key":"4628_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1038\/nature10842","volume":"483","author":"A Scally","year":"2012","unstructured":"Scally A, Dutheil JY, Hillier LW, Jordan GE, Goodhead I, Herrero J, Hobolth A, Lappalainen T, Mailund T, Marques-Bonet T, McCarthy S, Montgomery SH, Schwalie PC, Tang YA, Ward MC, Xue Y, Yngvadottir B, Alkan C, Andersen LN, Ayub Q, Ball EV, Beal K, Bradley BJ, Chen Y, Clee CM, Fitzgerald S, Graves TA, Gu Y, Heath P, Heger A et al: Insights into hominid evolution from the gorilla genome sequence. Nature. 2012, 483: 169-175. 10.1038\/nature10842.","journal-title":"Nature"},{"key":"4628_CR14","doi-asserted-by":"publisher","first-page":"1640","DOI":"10.1101\/gr.124461.111","volume":"21","author":"M Ventura","year":"2011","unstructured":"Ventura M, Catacchio CR, Alkan C, Marques-Bonet T, Sajjadian S, Graves TA, Hormozdiari F, Navarro A, Malig M, Baker C, Lee C, Turner EH, Chen L, Kidd JM, Archidiacono N, Shendure J, Wilson RK, Eichler EE: Gorilla genome structural variation reveals evolutionary parallelisms with chimpanzee. Genome Res. 2011, 21: 1640-1649. 10.1101\/gr.124461.111.","journal-title":"Genome Res"},{"key":"4628_CR15","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1126\/science.1188021","volume":"328","author":"RE Green","year":"2010","unstructured":"Green RE, Krause J, Briggs AW, Maricic T, Stenzel U, Kircher M, Patterson N, Li H, Zhai W, Fritz MHY, Hansen NF, Durand EY, Malaspinas AS, Jensen JD, Marques-Bonet T, Alkan C, Pr\u00fcfer K, Meyer M, Burbano HA, Good JM, Schultz R, Aximu-Petri A, Butthof A, H\u00f6ber B, H\u00f6ner B, Siegemund M, Weihmann A, Nusbaum C, Lander ES, Russ C et al: A draft sequence of the Neandertal genome. Science. 2010, 328: 710-722. 10.1126\/science.1188021.","journal-title":"Science"},{"key":"4628_CR16","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1038\/nature09710","volume":"468","author":"D Reich","year":"2010","unstructured":"Reich D, Green RE, Kircher M, Krause J, Patterson N, Durand EY, Viola B, Briggs AW, Stenzel U, Johnson PLF, Maricic T, Good JM, Marques-Bonet T, Alkan C, Fu Q, Mallick S, Li H, Meyer M, Eichler EE, Stoneking M, Richards M, Talamo S, Shunkov MV, Derevianko AP, Hublin JJ, Kelso J, Slatkin M, P\u00e4\u00e4bo S: Genetic history of an archaic hominin group from Denisova Cave in Siberia. Nature. 2010, 468: 1053-1060. 10.1038\/nature09710.","journal-title":"Nature"},{"key":"4628_CR17","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. Journal of Molecular Biology. 1981, 147: 195-195. 10.1016\/0022-2836(81)90087-5.","journal-title":"Journal of Molecular Biology"},{"key":"4628_CR18","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. Journal of Molecular Biology. 1970, 48: 443-453. 10.1016\/0022-2836(70)90057-4.","journal-title":"Journal of Molecular Biology"},{"key":"4628_CR19","volume-title":"A block-sorting lossless data compression algorithm","author":"M Burrows","year":"1994","unstructured":"Burrows M, Wheeler DJ, Burrows M, Wheeler DJ: A block-sorting lossless data compression algorithm. 1994"},{"key":"4628_CR20","volume-title":"ACM Transactions on Algorithms","author":"P Ferragina","year":"2007","unstructured":"Ferragina P, Manzini G, M\u00e4kinen V, Navarro G: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms. 2007, 3:"},{"key":"4628_CR21","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. Journal of Molecular Biology. 1990, 215: 403-410.","journal-title":"Journal of Molecular Biology"},{"key":"4628_CR22","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1038\/ng.437","volume":"41","author":"C Alkan","year":"2009","unstructured":"Alkan C, Kidd JM, Marques-Bonet T, Aksay G, Antonacci F, Hormozdiari F, Kitzman JO, Baker C, Malig M, Mutlu O, Sahinalp SC, Gibbs RA, Eichler EE: Personalized copy number and segmental duplication maps using next-generation sequencing. Nat Genet. 2009, 41: 1061-1067. 10.1038\/ng.437.","journal-title":"Nat Genet"},{"key":"4628_CR23","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, Hormozdiari F, Birol I, Eichler EE, Sahinalp SC: mrsFAST: a cache-oblivious algorithm for short-read mapping. Nat Methods. 2010, 7: 576-577. 10.1038\/nmeth0810-576.","journal-title":"Nat Methods"},{"key":"4628_CR24","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. 2009, 25: 1754-1760. 10.1093\/bioinformatics\/btp324.","journal-title":"Bioinformatics"},{"key":"4628_CR25","doi-asserted-by":"publisher","first-page":"e1000386","DOI":"10.1371\/journal.pcbi.1000386","volume":"5","author":"SM Rumble","year":"2009","unstructured":"Rumble SM, Lacroute P, Dalca AV, Fiume M, Sidow A, Brudno M: SHRiMP: Accurate Mapping of Short Color-space Reads. PLoS Comput Biol. 2009, 5: e1000386-10.1371\/journal.pcbi.1000386.","journal-title":"PLoS Comput Biol"},{"key":"4628_CR26","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, Li C, Weng L, Xie X: Hobbes: optimized gram-based methods for efficient read alignment. Nucleic Acids Research. 2011, 40: e41-","journal-title":"Nucleic Acids Research"},{"key":"4628_CR27","doi-asserted-by":"publisher","first-page":"1915","DOI":"10.1093\/bioinformatics\/btr303","volume":"27","author":"F Hormozdiari","year":"2011","unstructured":"Hormozdiari F, Hach F, Sahinalp SC, Eichler EE, Alkan C: Sensitive and fast mapping of di-base encoded reads. Bioinformatics. 2011, 27: 1915-1921. 10.1093\/bioinformatics\/btr303.","journal-title":"Bioinformatics"},{"key":"4628_CR28","doi-asserted-by":"publisher","first-page":"1646","DOI":"10.1101\/gr.088823.108","volume":"19","author":"D Weese","year":"2009","unstructured":"Weese D, Emde AK, Rausch T, D\u00f6ring A, Reinert K: RazerS--fast read mapping with sensitivity control. Genome Research. 2009, 19: 1646-1654. 10.1101\/gr.088823.108.","journal-title":"Genome Research"},{"key":"4628_CR29","volume-title":"Bioinformatics","author":"H Li","year":"2009","unstructured":"Li H, Durbin R: Fast and accurate short read alignment with Burrows-Wheeler Transform. Bioinformatics. 2009"},{"key":"4628_CR30","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, Salzberg S: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 2009, 10: R25-10.1186\/gb-2009-10-3-r25.","journal-title":"Genome Biol"},{"key":"4628_CR31","volume-title":"Bioinformatics","author":"Li","year":"2009","unstructured":"Li et al: SOAP2: an improved ultrafast tool for short read alignment. Bioinformatics. 2009"},{"key":"4628_CR32","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1038\/nrg2958","volume":"12","author":"C Alkan","year":"2011","unstructured":"Alkan C, Coe BP, Eichler EE: Genome structural variation discovery and genotyping. Nat Rev Genet. 2011, 12: 363-376. 10.1038\/nrg2958.","journal-title":"Nat Rev Genet"},{"key":"4628_CR33","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1038\/nature08795","volume":"463","author":"SC Schuster","year":"2010","unstructured":"Schuster SC, Miller W, Ratan A, Tomsho LP, Giardine B, Kasson LR, Harris RS, Petersen DC, Zhao F, Qi J, Alkan C, Kidd JM, Sun Y, Drautz DI, Bouard P, Muzny DM, Reid JG, Nazareth LV, Wang Q, Burhans R, Riemer C, Wittekindt NE, Moorjani P, Tindall EA, Danko CG, Teo WS, Buboltz AM, Zhang Z, Ma Q, Oosthuysen A et al: Complete Khoisan and Bantu genomes from southern Africa. Nature. 2010, 463: 943-947. 10.1038\/nature08795.","journal-title":"Nature"},{"key":"4628_CR34","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1038\/nature09708","volume":"470","author":"RE Mills","year":"2011","unstructured":"Mills RE, Walter K, Stewart C, Handsaker RE, Chen K, Alkan C, Abyzov A, Yoon SC, Ye K, Cheetham RK, Chinwalla A, Conrad DF, Fu Y, Grubert F, Hajirasouliha I, Hormozdiari F, Iakoucheva LM, Iqbal Z, Kang S, Kidd JM, Konkel MK, Korn J, Khurana E, Kural D, Lam HYK, Leng J, Li R, Li Y, Lin CY, Luo R et al: Mapping copy number variation by population-scale genome sequencing. Nature. 2011, 470: 59-65. 10.1038\/nature09708.","journal-title":"Nature"},{"key":"4628_CR35","volume-title":"Soviet Physics Doklady","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein VI: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady. 1966"},{"key":"4628_CR36","volume-title":"Emery's Elements of Medical Genetics","author":"P Turnpenny","year":"2005","unstructured":"Turnpenny P, Ellard S: Emery's Elements of Medical Genetics. 2005, 12","edition":"12"},{"key":"4628_CR37","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1038\/nature11128","volume":"486","author":"K Pr\u00fcfer","year":"2012","unstructured":"Pr\u00fcfer K, Munch K, Hellmann I, Akagi K, Miller JR, Walenz B, Koren S, Sutton G, Kodira C, Winer R, Knight JR, Mullikin JC, Meader SJ, Ponting CP, Lunter G, Higashino S, Hobolth A, Dutheil J, Karako\u00e7 E, Alkan C, Sajjadian S, Catacchio CR, Ventura M, Marques-Bonet T, Eichler EE, Andr\u00e9 C, Atencia R, Mugisha L, Junhold J, Patterson N et al: The bonobo genome compared with the chimpanzee and human genomes. Nature. 2012, 486: 527-531.","journal-title":"Nature"},{"key":"4628_CR38","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1038\/nature09687","volume":"469","author":"DP Locke","year":"2011","unstructured":"Locke DP, Hillier LW, Warren WC, Worley KC, Nazareth LV, Muzny DM, Yang SP, Wang Z, Chinwalla AT, Minx P, Mitreva M, Cook L, Delehaunty KD, Fronick C, Schmidt H, Fulton LA, Fulton RS, Nelson JO, Magrini V, Pohl C, Graves TA, Markovic C, Cree A, Dinh HH, Hume J, Kovar CL, Fowler GR, Lunter G, Meader S, Heger A et al: Comparative and demographic analysis of orang-utan genomes. Nature. 2011, 469: 529-533. 10.1038\/nature09687.","journal-title":"Nature"},{"key":"4628_CR39","unstructured":"Intel: Intel\u00ae SSE4 Programming Reference. [http:\/\/softwarecommunity.intel.com\/isn\/Downloads\/Intel%20SSE4%20Programming%20Reference.pdf]"}],"container-title":["BMC Genomics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2164-14-S1-S13.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2164-14-S1-S13\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2164-14-S1-S13.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T21:38:50Z","timestamp":1630532330000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcgenomics.biomedcentral.com\/articles\/10.1186\/1471-2164-14-S1-S13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":39,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["4628"],"URL":"https:\/\/doi.org\/10.1186\/1471-2164-14-s1-s13","relation":{},"ISSN":["1471-2164"],"issn-type":[{"value":"1471-2164","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]},"assertion":[{"value":"21 January 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S13"}}