{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,6]],"date-time":"2026-11-06T02:30:33Z","timestamp":1793932233171,"version":"4.8.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T00:00:00Z","timestamp":1757462400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T00:00:00Z","timestamp":1757462400000},"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":["Nat Biotechnol"],"published-print":{"date-parts":[[2026,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The size of microbial sequence databases continues to grow beyond the abilities of existing alignment tools. We introduce LexicMap, a nucleotide sequence alignment tool for efficiently querying moderate-length sequences (&gt;250\u2009bp) such as a gene, plasmid or long read against up to millions of prokaryotic genomes. We construct a small set of probe\n                    <jats:italic>k<\/jats:italic>\n                    -mers, which are selected to efficiently sample the entire database to be indexed such that every 250-bp window of each database genome contains multiple seed\n                    <jats:italic>k<\/jats:italic>\n                    -mers, each with a shared prefix with one of the probes. Storing these seeds in a hierarchical index enables fast and low-memory alignment. We benchmark both accuracy and potential to scale to databases of millions of bacterial genomes, showing that LexicMap achieves comparable accuracy to state-of-the-art methods but with greater speed and lower memory use. Our method supports querying at scale and within minutes, which will be useful for many biological applications across epidemiology, ecology and evolution.\n                  <\/jats:p>","DOI":"10.1038\/s41587-025-02812-8","type":"journal-article","created":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T09:03:32Z","timestamp":1757495012000},"page":"1383-1390","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Efficient sequence alignment against millions of prokaryotic genomes with LexicMap"],"prefix":"10.1038","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8099-8258","authenticated-orcid":false,"given":"Wei","family":"Shen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5360-1254","authenticated-orcid":false,"given":"John A.","family":"Lees","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8466-7547","authenticated-orcid":false,"given":"Zamin","family":"Iqbal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,9,10]]},"reference":[{"key":"2812_CR1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-421","volume":"10","author":"C Camacho","year":"2009","unstructured":"Camacho, C. et al. BLAST+: architecture and applications. BMC Bioinformatics 10, 421 (2009).","journal-title":"BMC Bioinformatics"},{"key":"2812_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\u2013Wheeler transform. Bioinformatics 25, 1754\u20131760 (2009).","journal-title":"Bioinformatics"},{"key":"2812_CR3","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead, B. & Salzberg, S. L. Fast gapped-read alignment with Bowtie 2. Nat. Methods 9, 357\u2013359 (2012).","journal-title":"Nat. Methods"},{"key":"2812_CR4","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 34, 3094\u20133100 (2018).","journal-title":"Bioinformatics"},{"key":"2812_CR5","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman, S. B. & Wunsch, C. D. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48, 443\u2013453 (1970).","journal-title":"J. Mol. Biol."},{"key":"2812_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith, T. F. & Waterman, M. S. Identification of common molecular subsequences. J. Mol. Biol. 147, 195\u2013197 (1981).","journal-title":"J. Mol. Biol."},{"key":"2812_CR7","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. 162, 705\u2013708 (1982).","journal-title":"J. Mol. Biol."},{"key":"2812_CR8","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1093\/bioinformatics\/btaa777","volume":"37","author":"S Marco-Sola","year":"2021","unstructured":"Marco-Sola, S., Moure, J. C., Moreto, M. & Espinosa, A. Fast gap-affine pairwise alignment using the wavefront algorithm. Bioinformatics 37, 456\u2013463 (2021).","journal-title":"Bioinformatics"},{"key":"2812_CR9","doi-asserted-by":"publisher","first-page":"btad487","DOI":"10.1093\/bioinformatics\/btad487","volume":"39","author":"D Liu","year":"2023","unstructured":"Liu, D. & Steinegger, M. Block Aligner: an adaptive SIMD-accelerated aligner for sequences and position-specific scoring matrices. Bioinformatics 39, btad487 (2023).","journal-title":"Bioinformatics"},{"key":"2812_CR10","doi-asserted-by":"publisher","first-page":"btae032","DOI":"10.1093\/bioinformatics\/btae032","volume":"40","author":"R Groot Koerkamp","year":"2024","unstructured":"Groot Koerkamp, R. & Ivanov, P. Exact global alignment using A* with chaining seed heuristic and match pruning. Bioinformatics 40, btae032 (2024).","journal-title":"Bioinformatics"},{"key":"2812_CR11","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1038\/s41592-023-01970-4","volume":"20","author":"AV Bzikadze","year":"2023","unstructured":"Bzikadze, A. V. & Pevzner, P. A. UniAligner: a parameter-free framework for fast sequence alignment. Nat. Methods 20, 1346\u20131354 (2023).","journal-title":"Nat. Methods"},{"key":"2812_CR12","doi-asserted-by":"publisher","first-page":"qzae025","DOI":"10.1093\/gpbjnl\/qzae025","volume":"22","author":"H Shao","year":"2024","unstructured":"Shao, H. & Ruan, J. BSAlign: a library for nucleotide sequence alignment. Genomics Proteomics Bioinformatics 22, qzae025 (2024).","journal-title":"Genomics Proteomics Bioinformatics"},{"key":"2812_CR13","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1038\/s41592-025-02625-2","volume":"22","author":"K B\u0159inda","year":"2025","unstructured":"B\u0159inda, K. et al. Efficient and robust search of microbial genomes via phylogenetic compression. Nat. Methods 22, 692\u2013697 (2025).","journal-title":"Nat. Methods"},{"key":"2812_CR14","doi-asserted-by":"publisher","first-page":"e3001421","DOI":"10.1371\/journal.pbio.3001421","volume":"19","author":"GA Blackwell","year":"2021","unstructured":"Blackwell, G. A. et al. Exploring bacterial diversity via a curated and searchable snapshot of archived DNA sequences. PLOS Biol. 19, e3001421 (2021).","journal-title":"PLOS Biol."},{"key":"2812_CR15","doi-asserted-by":"publisher","first-page":"1787","DOI":"10.1038\/s41564-023-01472-1","volume":"8","author":"F Lassalle","year":"2023","unstructured":"Lassalle, F. et al. Genomic epidemiology reveals multidrug resistant plasmid spread between Vibrio cholerae lineages in Yemen. Nat. Microbiol. 8, 1787\u20131798 (2023).","journal-title":"Nat. Microbiol."},{"key":"2812_CR16","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-023-37672-w","volume":"14","author":"LCE Mason","year":"2023","unstructured":"Mason, L. C. E. et al. The evolution and international spread of extensively drug resistant Shigella sonnei. Nat. Commun. 14, 1983 (2023).","journal-title":"Nat. Commun."},{"key":"2812_CR17","doi-asserted-by":"publisher","first-page":"e0083121","DOI":"10.1128\/msystems.00831-21","volume":"7","author":"Y Hu","year":"2022","unstructured":"Hu, Y., Moran, R. A., Blackwell, G. A., McNally, A. & Zong, Z. Fine-scale reconstruction of the evolution of FII-33 multidrug resistance plasmids enables high-resolution genomic surveillance. mSystems 7, e0083121 (2022).","journal-title":"mSystems"},{"key":"2812_CR18","doi-asserted-by":"publisher","first-page":"2308","DOI":"10.3201\/eid2811.220615","volume":"28","author":"WK Smits","year":"2022","unstructured":"Smits, W. K. et al. Sequence-based identification of metronidazole-resistant Clostridioides difficile isolates. Emerg. Infect. Dis. 28, 2308\u20132311 (2022).","journal-title":"Emerg. Infect. Dis."},{"key":"2812_CR19","doi-asserted-by":"publisher","first-page":"e2212694120","DOI":"10.1073\/pnas.2212694120","volume":"120","author":"K Tamadonfar","year":"2023","unstructured":"Tamadonfar, K. et al. Structure\u2013function correlates of fibrinogen binding by Acinetobacter adhesins critical in catheter-associated urinary tract infections. Proc. Natl Acad. Sci. USA 120, e2212694120 (2023).","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2812_CR20","doi-asserted-by":"publisher","first-page":"e14446","DOI":"10.1111\/1751-7915.14446","volume":"17","author":"NJ Croucher","year":"2024","unstructured":"Croucher, N. J. Immune interface interference vaccines: an evolution-informed approach to anti-bacterial vaccine design. Microb. Biotechnol. 17, e14446 (2024).","journal-title":"Microb. Biotechnol."},{"key":"2812_CR21","doi-asserted-by":"publisher","first-page":"e78454","DOI":"10.7554\/eLife.78454","volume":"11","author":"TM Smith","year":"2022","unstructured":"Smith, T. M. et al. Rapid adaptation of a complex trait during experimental evolution of Mycobacterium tuberculosis. eLife 11, e78454 (2022).","journal-title":"eLife"},{"key":"2812_CR22","doi-asserted-by":"publisher","first-page":"D785","DOI":"10.1093\/nar\/gkab776","volume":"50","author":"DH Parks","year":"2022","unstructured":"Parks, D. H. et al. GTDB: an ongoing census of bacterial and archaeal diversity through a phylogenetically consistent, rank normalized and complete genome-based taxonomy. Nucleic Acids Res. 50, D785\u2013D794 (2022).","journal-title":"Nucleic Acids Res."},{"key":"2812_CR23","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-021-02473-1","volume":"22","author":"RM Colquhoun","year":"2021","unstructured":"Colquhoun, R. M. et al. Pandora: nucleotide-resolution bacterial pan-genomics with reference graphs. Genome Biol. 22, 267 (2021).","journal-title":"Genome Biol."},{"key":"2812_CR24","doi-asserted-by":"publisher","first-page":"D777","DOI":"10.1093\/nar\/gkad943","volume":"52","author":"TSB Schmidt","year":"2024","unstructured":"Schmidt, T. S. B. et al. SPIRE: a searchable, planetary-scale microbiome resource. Nucleic Acids Res. 52, D777\u2013D783 (2024).","journal-title":"Nucleic Acids Res."},{"key":"2812_CR25","doi-asserted-by":"publisher","first-page":"D134","DOI":"10.1093\/nar\/gkad903","volume":"52","author":"EW Sayers","year":"2024","unstructured":"Sayers, E. W. et al. GenBank 2024 update. Nucleic Acids Res. 52, D134\u2013D137 (2024).","journal-title":"Nucleic Acids Res."},{"key":"2812_CR26","doi-asserted-by":"publisher","first-page":"D762","DOI":"10.1093\/nar\/gkad988","volume":"52","author":"DH Haft","year":"2024","unstructured":"Haft, D. H. et al. RefSeq and the prokaryotic genome annotation pipeline in the age of metagenomes. Nucleic Acids Res. 52, D762\u2013D769 (2024).","journal-title":"Nucleic Acids Res."},{"key":"2812_CR27","doi-asserted-by":"publisher","unstructured":"Hunt, M., Lima, L., Shen, W., Lees, J. & Iqbal, Z. AllTheBacteria\u2014all bacterial genomes assembled, available and searchable. Preprint at bioRxiv https:\/\/doi.org\/10.1101\/2024.03.08.584059 (2024).","DOI":"10.1101\/2024.03.08.584059"},{"key":"2812_CR28","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1038\/nbt.3988","volume":"35","author":"M Steinegger","year":"2017","unstructured":"Steinegger, M. & S\u00f6ding, J. MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets. Nat. Biotechnol. 35, 1026\u20131028 (2017).","journal-title":"Nat. Biotechnol."},{"key":"2812_CR29","doi-asserted-by":"crossref","unstructured":"Bingmann, T., Bradley, P., Gauger, F. & Iqbal, Z. COBS: a compact bit-sliced signature index. In Proc. 26th International Symposium on String Processing and Information Retrieval (eds Brisaboa, N. R. & Puglisi, S. J.) (Springer, 2019).","DOI":"10.1007\/978-3-030-32686-9_21"},{"key":"2812_CR30","doi-asserted-by":"publisher","first-page":"btac845","DOI":"10.1093\/bioinformatics\/btac845","volume":"39","author":"W Shen","year":"2023","unstructured":"Shen, W. et al. KMCP: accurate metagenomic profiling of both prokaryotic and viral populations by pseudo-mapping. Bioinformatics 39, btac845 (2023).","journal-title":"Bioinformatics"},{"key":"2812_CR31","doi-asserted-by":"publisher","first-page":"btae717","DOI":"10.1093\/bioinformatics\/btae717","volume":"40","author":"H Li","year":"2024","unstructured":"Li, H. BWT construction and search at the terabase scale. Bioinformatics 40, btae717 (2024).","journal-title":"Bioinformatics"},{"key":"2812_CR32","doi-asserted-by":"publisher","first-page":"btad652","DOI":"10.1093\/bioinformatics\/btad652","volume":"39","author":"G Greenberg","year":"2023","unstructured":"Greenberg, G., Ravi, A. N. & Shomorony, I. LexicHash: sequence similarity estimation via lexicographic comparison of hashes. Bioinformatics 39, btad652 (2023).","journal-title":"Bioinformatics"},{"key":"2812_CR33","doi-asserted-by":"publisher","first-page":"btae629","DOI":"10.1093\/bioinformatics\/btae629","volume":"40","author":"G Mar\u00e7ais","year":"2024","unstructured":"Mar\u00e7ais, G., Elder, C. S. & Kingsford, C. k-nonical space: sketching with reverse complements. Bioinformatics 40, btae629 (2024).","journal-title":"Bioinformatics"},{"key":"2812_CR34","doi-asserted-by":"publisher","first-page":"1316","DOI":"10.21105\/joss.01316","volume":"4","author":"RR Wick","year":"2019","unstructured":"Wick, R. R. Badread: simulation of error-prone long reads. J. Open Source Softw. 4, 1316 (2019).","journal-title":"J. Open Source Softw."},{"key":"2812_CR35","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1038\/s41559-019-0854-x","volume":"3","author":"MA Brockhurst","year":"2019","unstructured":"Brockhurst, M. A. et al. Assessing evolutionary risks of resistance for new antimicrobial therapies. Nat. Ecol. Evol. 3, 515\u2013517 (2019).","journal-title":"Nat. Ecol. Evol."},{"key":"2812_CR36","doi-asserted-by":"publisher","first-page":"e0282622","DOI":"10.1128\/spectrum.02826-22","volume":"11","author":"MG Lopez","year":"2023","unstructured":"Lopez, M. G. et al. Deciphering the tangible spatio-temporal spread of a 25-year tuberculosis outbreak boosted by social determinants. Microbiol. Spectr. 11, e0282622 (2023).","journal-title":"Microbiol. Spectr."},{"key":"2812_CR37","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1089\/cmb.2006.13.1028","volume":"13","author":"A Morgulis","year":"2006","unstructured":"Morgulis, A., Gertz, E. M., Sch\u00e4ffer, A. A. & Agarwala, R. A fast and symmetric DUST implementation to mask low-complexity DNA sequences. J. Comput. Biol. 13, 1028\u20131040 (2006).","journal-title":"J. Comput. Biol."},{"key":"2812_CR38","doi-asserted-by":"crossref","unstructured":"Dean, J. Challenges in building large-scale information retrieval systems: invited talk. In Proc. Second ACM International Conference on Web Search and Data Mining (eds Baeza-Yates, R., Boldi, P., Ribeiro-Neto, B. & Barla Cambazoglu, B.) (Association for Computing Machinery, 2009).","DOI":"10.1145\/1498759.1498761"},{"key":"2812_CR39","doi-asserted-by":"publisher","first-page":"e10805","DOI":"10.7717\/peerj.10805","volume":"9","author":"R Edgar","year":"2021","unstructured":"Edgar, R. Syncmers are more sensitive than minimizers for selecting conserved kmers in biological sequences. PeerJ 9, e10805 (2021).","journal-title":"PeerJ"},{"key":"2812_CR40","doi-asserted-by":"publisher","first-page":"2264","DOI":"10.1073\/pnas.87.6.2264","volume":"87","author":"S Karlin","year":"1990","unstructured":"Karlin, S. & Altschul, S. F. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proc. Natl Acad. Sci. USA 87, 2264\u20132268 (1990).","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2812_CR41","doi-asserted-by":"publisher","first-page":"e191","DOI":"10.1002\/imt2.191","volume":"3","author":"W Shen","year":"2024","unstructured":"Shen, W., Sipos, B. & Zhao, L. SeqKit2: a Swiss army knife for sequence and alignment processing. iMeta 3, e191 (2024).","journal-title":"iMeta"},{"key":"2812_CR42","doi-asserted-by":"publisher","unstructured":"Shen, W., Lees, J. & Iqbal, Z. Archived code and data for analysis in LexicMap paper. Zenodo https:\/\/doi.org\/10.5281\/zenodo.15628530 (2025).","DOI":"10.5281\/zenodo.15628530"},{"key":"2812_CR43","doi-asserted-by":"publisher","unstructured":"Shen, W., Lees, J. & Iqbal, Z. Archived code repository for LexicMap. Zenodo https:\/\/doi.org\/10.5281\/zenodo.15197523 (2025).","DOI":"10.5281\/zenodo.15197523"}],"container-title":["Nature Biotechnology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s41587-025-02812-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41587-025-02812-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41587-025-02812-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T20:44:18Z","timestamp":1786481058000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s41587-025-02812-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,10]]},"references-count":43,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["2812"],"URL":"https:\/\/doi.org\/10.1038\/s41587-025-02812-8","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2024.08.30.610459","asserted-by":"object"}],"is-basis-for":[{"id-type":"doi","id":"10.52843\/cassyni.wvwlwh","asserted-by":"object"},{"id-type":"doi","id":"10.52843\/cassyni.1rst3f","asserted-by":"object"}]},"ISSN":["1087-0156","1546-1696"],"issn-type":[{"value":"1087-0156","type":"print"},{"value":"1546-1696","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,10]]},"assertion":[{"value":"13 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Ethics"}}]}}