LexicMap: efficient sequence alignment against millions of prokaryotic genomes

Alignment against a database of genomes is a fundamental operation in bioinformatics, popularized by BLAST. However, the rate at which microbial genomes are sequenced has continued to increase, and there are now datasets in the millions, far beyond the abilities of existing alignment tools. We introduce LexicMap, a nucleotide sequence alignment tool for efficiently querying moderate length sequences (>250 bp) such as a gene, plasmid or long read against up to millions of prokaryotic genomes. A key innovation is to construct a small set of probe k-mers (e.g. n = 20,000) 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 k-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 as the query diverges from the match in the database, and potential to scale to databases of millions of bacterial genomes, showing that LexicMap achieves comparable accuracy with state-of-the-art, but with greater speed and lower memory use. We then benchmark LexicMap on small/diverse (GTDB) and large/redundant (AllTheBacteria and GenBank+RefSeq) databases. Alignment of a single gene against 2.34 million prokaryotic genomes from GenBank and RefSeq takes 3 (rare gene) to 33 (16S rRNA gene) minutes. Full alignment against all bacterial genomes is now possible in minutes with modest resources, supporting querying at scale which will be useful for many biological applications across epidemiology, ecology and evolution. LexicMap produces output in standard formats including that of BLAST and is available under MIT license at https://github.com/shenwei356/LexicMap.