BSAlign: A Library for Nucleotide Sequence Alignment

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Accurate nucleotide sequence alignment is crucial for genomics research.
• Classic dynamic programming (DP) algorithms offer optimal results but are computationally expensive for large datasets.
• Existing acceleration methods focus on data structures, parallelism, or search space reduction individually.

Purpose of the Study:

• To develop an ultra-fast and accurate nucleotide sequence alignment algorithm.
• To combine multiple optimization strategies for enhanced performance.
• To provide a practical tool for large-scale genomic sequence analysis.

Main Methods:

• Developed the Banded Striped Aligner (BSAlign) library.
• Integrated novel methods combining data structure redesign (striped SIMD), increased parallelism, and reduced search space (banded DP).
• Implemented features like active F-loop in striped vectorization and striped move in banded DP.

Main Results:

• BSAlign achieves ultra-fast alignment speeds while maintaining accuracy.
• Demonstrated a 2-fold speed-up over other SIMD-based implementations for regular pairwise alignment.
• Achieved 1.5-fold to 4-fold speed-up for edit distance-based alignment of long reads.

Conclusions:

• BSAlign effectively combines multiple acceleration perspectives for superior performance.
• The library offers significant speed improvements for both regular and edit distance pairwise alignments.
• BSAlign is a valuable tool for accelerating large-scale genomics research.