block aligner

block aligner implements SIMD-accelerated sequence alignment in Rust for global and X-drop affine gap penalty alignments of nucleotide and protein sequences.

Key Features:

• Adaptive Block-Based Algorithm: Employs an adaptive block-based algorithm that greedily shifts and expands blocks of computed scores to span large gaps.
• Partial DP Computation: Computes only a fraction of the dynamic programming (DP) matrix to reduce computation compared to full DP.
• SIMD Acceleration: Leverages Single Instruction Multiple Data (SIMD) instructions to accelerate score computations.
• Performance: Demonstrates up to ninefold speed improvement over Farrar’s algorithm for protein global alignments in experimental comparisons.
• Supported Alignment Modes: Supports global alignments and X-drop affine gap penalty alignments.
• Sequence Types: Applicable to both nucleotide and protein sequence alignment.
• Implementation: Implemented as a Rust library.
• Accuracy Trade-off: Uses a greedy approximation that does not guarantee full DP optimality but shows high empirical accuracy on realistic datasets.

Scientific Applications:

• Global Alignments: Computes global sequence alignments for nucleotide and protein sequences as a faster alternative to conventional DP on realistic datasets.
• X-Drop Affine Gap Penalty Alignments: Performs X-drop affine gap penalty alignments to identify regions of similarity potentially interrupted by gaps.

Methodology:

Implements an adaptive, greedy block-based dynamic programming variant that shifts and grows blocks of scores, computes a subset of the DP matrix, and uses SIMD instructions; provided as a Rust library and supporting global and X-drop affine gap penalty alignments.