BWA-MEME

BWA-MEME implements a learned-index-accelerated seeding algorithm to perform SMEM (Seed-and-Extend Match) searches for short-read alignment against a reference genome, improving seeding throughput in NGS pipelines.

Key Features:

• Learned-index suffix array search: Incorporates learned indices into the suffix array search algorithm specifically tailored for SMEM searches during the seeding phase.
• Seeding performance: Achieves up to a 3.45-fold increase in seeding throughput compared to BWA-MEM2.
• Instruction reduction: Reduces the number of CPU instructions required by 4.60 times.
• Memory access optimization: Reduces memory accesses by 8.77 times to address the primary memory-access bottleneck in seeding.
• Cache efficiency: Lowers Last-Level Cache (LLC) misses by 2.21 times.
• Output compatibility: Produces output identical to BWA-MEM2 in Sequence Alignment/Map (SAM) format.

Scientific Applications:

• Short-read alignment: Accelerates SMEM-based seeding for alignment of Illumina-style short reads against reference genomes.
• Large-scale genomic studies: Enables faster processing of high-throughput NGS datasets for population- and cohort-scale projects.
• Variant discovery and disease association: Speeds alignment steps used in pipelines for SNP/indel discovery and association studies.
• Evolutionary genomics: Facilitates rapid alignment required for comparative genomics and phylogenomic analyses.

Methodology:

Incorporates learned indices (machine-learning models that predict substring positions) into the suffix array search algorithm to accelerate SMEM searches during the seeding phase.