An efficient Burrows-Wheeler transform-based aligner for short read mapping.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Read mapping is a critical but computationally intensive bottleneck in modern computational biology.
• Exploding sequencing throughput necessitates faster and more efficient read alignment tools.
• Existing Burrows-Wheeler Transform (BWT)-based aligners face challenges in speed despite their accuracy.

Purpose of the Study:

• To develop an efficient Burrows-Wheeler Transform-based aligner for next-generation sequencing (NGS) short reads.
• To accelerate the read mapping process without compromising accuracy or significantly increasing memory usage.
• To provide a competitive alternative to existing state-of-the-art BWT aligners.

Main Methods:

• Proposed a difference-aware classification strategy for economical read searching.
• Implemented acceleration techniques including seed pruning and redesigned LF calculation for faster queries.
• Utilized heuristic verification with low-distortion string embedding and wavefront alignment for efficient mapping.

Main Results:

• The developed aligner is 1.3-1.4 times faster than state-of-the-art BWT methods (bowtie2, bwa-MEM, hisat2) for 101bp reads.
• Achieved a 1.5-13 times speedup for longer reads (750bp-1000bp) compared to existing BWT methods.
• Demonstrated comparable memory usage and accuracy to other BWT-based aligners, while noting hash-based methods are faster.

Conclusions:

• The novel BWT-based aligner significantly improves read mapping efficiency for NGS data.
• The implemented acceleration strategies effectively reduce computational bottlenecks in read alignment.
• This tool offers a faster, accurate, and memory-efficient solution for computational biology applications.