{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T14:27:59Z","timestamp":1776004079285,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T00:00:00Z","timestamp":1714780800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T00:00:00Z","timestamp":1714780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["872539"],"award-info":[{"award-number":["872539"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["31A532B"],"award-info":[{"award-number":["31A532B"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A533A"],"award-info":[{"award-number":["031A533A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A533B"],"award-info":[{"award-number":["031A533B"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A534A"],"award-info":[{"award-number":["031A534A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A535A"],"award-info":[{"award-number":["031A535A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A537A"],"award-info":[{"award-number":["031A537A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A537B"],"award-info":[{"award-number":["031A537B"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A537C"],"award-info":[{"award-number":["031A537C"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A537D"],"award-info":[{"award-number":["031A537D"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["031A538A"],"award-info":[{"award-number":["031A538A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["2138585"],"award-info":[{"award-number":["2138585"]}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"crossref","award":["R01GM146462"],"award-info":[{"award-number":["R01GM146462"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005721","name":"Universit\u00e4t Bielefeld","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005721","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"Abstract<\/jats:title>\n \n Background<\/jats:title>\n Given a sequencing read, the broad goal of read mapping is to find the location(s) in the reference genome that have a \u201csimilar sequence\u201d. Traditionally, \u201csimilar sequence\u201d was defined as having a high alignment score and read mappers were viewed as heuristic solutions to this well-defined problem. For sketch-based mappers, however, there has not been a problem formulation to capture what problem an exact sketch-based mapping algorithm should solve. Moreover, there is no sketch-based method that can find all possible mapping positions for a read above a certain score threshold.<\/jats:p>\n <\/jats:sec>\n \n Results<\/jats:title>\n \n In this paper, we formulate the problem of read mapping at the level of sequence sketches. We give an exact dynamic programming algorithm that finds all hits above a given similarity threshold. It runs in\n \n \n $$\\mathcal {O} (|t| + |p| + \\ell ^2)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n |<\/mml:mo>\n t<\/mml:mi>\n |<\/mml:mo>\n +<\/mml:mo>\n |<\/mml:mo>\n p<\/mml:mi>\n |<\/mml:mo>\n +<\/mml:mo>\n \n \u2113<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n time and\n \n \n $$\\mathcal {O} (\\ell \\log \\ell )$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \u2113<\/mml:mi>\n log<\/mml:mo>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n space, where |\n t<\/jats:italic>\n | is the number of\n \n \n $$k$$<\/jats:tex-math>\n \n k<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -mers inside the sketch of the reference, |\n p<\/jats:italic>\n | is the number of\n \n \n $$k$$<\/jats:tex-math>\n \n k<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -mers inside the read\u2019s sketch and\n \n \n $$\\ell$$<\/jats:tex-math>\n \n \u2113<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the number of times that\n \n \n $$k$$<\/jats:tex-math>\n \n k<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -mers from the pattern sketch occur in the sketch of the text. We evaluate our algorithm\u2019s performance in mapping long reads to the T2T assembly of human chromosome Y, where ampliconic regions make it desirable to find all good mapping positions. For an equivalent level of precision as minimap2, the recall of our algorithm is 0.88, compared to only 0.76 of minimap2.\n <\/jats:p>\n <\/jats:sec>","DOI":"10.1186\/s13015-024-00261-7","type":"journal-article","created":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T08:01:49Z","timestamp":1714809709000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["ESKEMAP: exact sketch-based read mapping"],"prefix":"10.1186","volume":"19","author":[{"given":"Tizian","family":"Schulz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,4]]},"reference":[{"issue":"18","key":"261_CR1","doi-asserted-by":"publisher","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","volume":"34","author":"H Li","year":"2018","unstructured":"Li H. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics. 2018;34(18):3094\u2013100.","journal-title":"Bioinformatics"},{"issue":"1","key":"261_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-023-02972-3","volume":"24","author":"K Sahlin","year":"2023","unstructured":"Sahlin K, Baudeau T, Cazaux B, Marchet C. A survey of mapping algorithms in the long-reads era. Genom Biol. 2023;24(1):1\u201323.","journal-title":"Genom Biol"},{"key":"261_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1038\/nmeth.1374","volume":"6","author":"P Medvedev","year":"2009","unstructured":"Medvedev P, Stanciu M, Brudno M. Computational methods for discovering structural variation with next-generation sequencing. Nat Method. 2009;6:13.","journal-title":"Nat Method"},{"issue":"10","key":"261_CR4","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, et al. Personalized copy number and segmental duplication maps using next-generation sequencing. Nat Genet. 2009;41(10):1061\u20137.","journal-title":"Nat Genet"},{"key":"261_CR5","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1038\/s41592-022-01457-8","volume":"19","author":"C Jain","year":"2022","unstructured":"Jain C, Rhie A, Hansen NF, Koren S, Phillippy AM. Long-read mapping to repetitive reference sequences using Winnowmap2. Nat Method. 2022;19:705\u201310.","journal-title":"Nat Method"},{"issue":"9","key":"261_CR6","doi-asserted-by":"publisher","first-page":"1394","DOI":"10.1093\/bioinformatics\/btw753","volume":"33","author":"M \u0160o\u0161i\u0107","year":"2017","unstructured":"\u0160o\u0161i\u0107 M, \u0160iki\u0107 M. Edlib: a c\/c++ library for fast, exact sequence alignment using edit distance. Bioinformatics. 2017;33(9):1394\u20135.","journal-title":"Bioinformatics"},{"issue":"18","key":"261_CR7","doi-asserted-by":"publisher","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","volume":"20","author":"M Roberts","year":"2004","unstructured":"Roberts M, Hayes W, Hunt BR, Mount SM, Yorke JA. Reducing storage requirements for biological sequence comparison. Bioinformatics. 2004;20(18):3363\u20139.","journal-title":"Bioinformatics"},{"key":"261_CR8","doi-asserted-by":"crossref","unstructured":"Schleimer S, Wilkerson DS, Aiken A. Winnowing: Local algorithms for document fingerprinting. In: Proceedings of the 22nd International Conference on Management of Data (SIGMOD 2003), 2003;76\u201385.","DOI":"10.1145\/872757.872770"},{"key":"261_CR9","doi-asserted-by":"publisher","first-page":"10805","DOI":"10.7717\/peerj.10805","volume":"9","author":"R Edgar","year":"2021","unstructured":"Edgar R. Syncmers are more sensitive than minimizers for selecting conserved k-mers in biological sequences. Peer J. 2021;9:10805.","journal-title":"Peer J"},{"key":"261_CR10","doi-asserted-by":"publisher","unstructured":"Irber L, Brooks PT, Reiter T, Pierce-Ward NT, Hera MR, Koslicki D, Brown CT. Lightweight compositional analysis of metagenomes with FracMinHash and minimum metagenome covers. bioRxiv (2022) https:\/\/doi.org\/10.1101\/2022.01.11.475838.","DOI":"10.1101\/2022.01.11.475838"},{"key":"261_CR11","doi-asserted-by":"crossref","unstructured":"Hera MR, Pierce-Ward NT, Koslicki D. Debiasing FracMinHash and deriving confidence intervals for mutation rates across a wide range of evolutionary distances. bioRxiv (2022).","DOI":"10.1101\/2022.01.11.475870"},{"issue":"Supplement-1","key":"261_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1093\/bioinformatics\/btac244","volume":"38","author":"M Belbasi","year":"2022","unstructured":"Belbasi M, Blanca A, Harris RS, Koslicki D, Medvedev P. The minimizer jaccard estimator is biased and inconsistent. Bioinformatics. 2022;38(Supplement_1):169\u201376. https:\/\/doi.org\/10.1093\/bioinformatics\/btac244.","journal-title":"Bioinformatics"},{"issue":"2","key":"261_CR13","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1089\/cmb.2021.0431","volume":"29","author":"A Blanca","year":"2022","unstructured":"Blanca A, Harris RS, Koslicki D, Medvedev P. The statistics of k-mers from a sequence undergoing a simple mutation process without spurious matches. J Comput Biol. 2022;29(2):155\u201368.","journal-title":"J Comput Biol"},{"key":"261_CR14","doi-asserted-by":"publisher","unstructured":"Schulz T, Medvedev P. Exact Sketch-Based Read Mapping. In: Belazzougui, D., Ouangraoua, A. (eds.) 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 273, pp. 14\u201311419. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2023). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2023.14 . https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2023\/18640.","DOI":"10.4230\/LIPIcs.WABI.2023.14"},{"issue":"6588","key":"261_CR15","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1126\/science.abj6987","volume":"376","author":"S Nurk","year":"2022","unstructured":"Nurk S, Koren S, Rhie A, Rautiainen M, Bzikadze AV, Mikheenko A, Vollger MR, Altemose N, Uralsky L, Gershman A, et al. The complete sequence of a human genome. Science. 2022;376(6588):44\u201353.","journal-title":"Science"},{"issue":"42","key":"261_CR16","doi-asserted-by":"publisher","first-page":"26273","DOI":"10.1073\/pnas.2001749117","volume":"117","author":"M Cechova","year":"2020","unstructured":"Cechova M, Vegesna R, Tomaszkiewicz M, Harris RS, Chen D, Rangavittal S, Medvedev P, Makova KD. Dynamic evolution of great ape y chromosomes. Proc Natl Acad Sci. 2020;117(42):26273\u201380.","journal-title":"Proc Natl Acad Sci"},{"issue":"1","key":"261_CR17","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1038\/s41597-020-00743-4","volume":"7","author":"T Hon","year":"2020","unstructured":"Hon T, Mars K, Young G, Tsai Y-C, Karalius JW, Landolin JM, Maurer N, Kudrna D, Hardigan MA, Steiner CC, et al. Highly accurate long-read hifi sequencing data for five complex genomes. Sci Data. 2020;7(1):399.","journal-title":"Sci Data"},{"issue":"5","key":"261_CR18","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1093\/bioinformatics\/btaa835","volume":"37","author":"Y Ono","year":"2021","unstructured":"Ono Y, Asai K, Hamada M. Pbsim2: a simulator for long-read sequencers with a novel generative model of quality scores. Bioinformatics. 2021;37(5):589\u201395.","journal-title":"Bioinformatics"},{"issue":"3","key":"261_CR19","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. https:\/\/doi.org\/10.1016\/S0022-2836(05)80360-2.","journal-title":"J Mol Biol"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00261-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-024-00261-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00261-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T08:02:22Z","timestamp":1714809742000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-024-00261-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,4]]},"references-count":19,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["261"],"URL":"https:\/\/doi.org\/10.1186\/s13015-024-00261-7","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2023.06.21.545862","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,4]]},"assertion":[{"value":"1 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"19"}}