LexicMap

LexicMap performs efficient nucleotide sequence alignment of moderate-length sequences (>250 bp) such as genes, plasmids, and long reads against databases of millions of prokaryotic genomes to enable scalable large-dataset querying.

Key Features:

• Innovative Probek-mer Construction: Constructs a small set of probek-mers (e.g., 20,000) to sample entire databases and ensure every 250 bp window across each genome contains multiple seedk-mers with shared prefixes linked to these probes.
• Hierarchical Indexing: Employs a hierarchical index structure to store seedk-mers for rapid and memory-efficient lookup during alignment.
• Scalability and Performance: Maintains accuracy for divergent query sequences while providing faster runtimes and reduced memory usage, with benchmarks reporting alignment of a single gene against 2.34 million prokaryotic genomes in 3–33 minutes depending on gene rarity.
• Versatility Across Databases: Validated on diverse datasets including GTDB, AllTheBacteria, and GenBank+RefSeq, supporting both small/varied and large/redundant genomic databases.
• Standard Output Formats: Produces results in standard formats compatible with BLAST outputs.

Scientific Applications:

• Epidemiology: Enables large-scale querying to track pathogen evolution and spread across millions of prokaryotic genomes.
• Ecology: Supports analysis of microbial diversity and interactions by querying extensive genomic collections.
• Evolutionary Biology: Facilitates investigation of genetic variation and adaptation by comparing genes and plasmids across large prokaryotic databases.

Methodology:

Constructs a small set of probek-mers (e.g., 20,000) to sample databases, links seedk-mers with shared prefixes to probes within every 250 bp window, builds a hierarchical index to store seeds, and outputs BLAST-compatible results; benchmarks report 3–33 minutes to align a single gene against 2.34 million prokaryotic genomes.