BWA-MEME: BWA-MEM emulated with a machine learning approach

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Next-generation sequencing (NGS) generates vast amounts of data, necessitating efficient short-read alignment.
• Seeding, the process of finding exact substring matches, is a major performance bottleneck in read alignment.
• Current alignment algorithms suffer from performance limitations due to frequent memory accesses.

Purpose of the Study:

• To develop a novel short-read alignment software that addresses the seeding bottleneck.
• To leverage learned indices for efficient exact match searching in the seeding phase.
• To improve the overall speed and efficiency of short-read alignment.

Main Methods:

• Introduction of BWA-MEME, a short-read alignment software utilizing learned indices.
• Implementation of a practical and efficient seeding algorithm based on suffix array search.
• Addressing challenges in applying learned indices for Smith-Waterman exact match (SMEM) search.

Main Results:

• BWA-MEME achieves up to 3.45x speedup in seeding throughput compared to BWA-MEM2.
• Significant reductions in computational resources: 4.60x fewer instructions, 8.77x fewer memory accesses, and 2.21x fewer LLC misses.
• Identical Sequence Alignment/Map (SAM) output compared to BWA-MEM2, ensuring data integrity.

Conclusions:

• BWA-MEME represents a significant advancement in efficient short-read alignment by optimizing the seeding process.
• The use of learned indices offers a practical and effective solution to accelerate genomic data analysis.
• The software is available for academic use, promoting further research and development in the field.