Note
Archive Notice: This project is an educational and reference implementation of the Wavefront Alignment (WFA) algorithm and BiWFA in Rust. It is finished and archived; no active maintenance or feature development is planned.
wfa is an exact, sub-quadratic gap-affine pairwise sequence alignment engine written in pure Rust. It implements the Wavefront Alignment (WFA) algorithm (Marco-Sola et al., 2021) and the
-
Branchless 64-Bit LCP Extension:
- Compares 8 bytes per iteration using 64-bit word loads (
u64::from_le_bytes), XOR, and trailing-zero counting (tzcnt), skipping matching sequence stretches with zero branching.
- Compares 8 bytes per iteration using 64-bit word loads (
-
Zero-Centered WavefrontArena:
- Flat contiguous memory slab mapping diagonal offsets
$k \in [\text{lo}, \text{hi}]$ with$O(1)$ indexed access, eliminating heap allocations inside the score loop.
- Flat contiguous memory slab mapping diagonal offsets
-
Exact Gap-Affine Model:
- Supports 2-piece affine gap penalties (mismatch
$X$ , gap open$O$ , gap extend$E$ ) across Match ($M$ ), Insertion ($I$ ), and Deletion ($D$ ) wavefronts:$$I_s[k] = \max\left(M_{s - (O + E)}[k + 1] + 1, I_{s - E}[k + 1] + 1\right)$$ $$D_s[k] = \max\left(M_{s - (O + E)}[k - 1], D_{s - E}[k - 1]\right)$$ $$M_s[k] = \max\left(M_{s - X}[k] + 1, I_s[k], D_s[k]\right)$$
- Supports 2-piece affine gap penalties (mismatch
-
BiWFA Divide-and-Conquer (
$O(s)$ Peak Memory):- For long sequences, bounds memory consumption to
$O(s)$ via bidirectional wavefront expansion and midpoint stitching.
- For long sequences, bounds memory consumption to
-
Exact Gotoh DP Verifier Baseline:
- Built-in classical
$O(N \cdot M)$ dynamic programming solver used to rigorously verify 100% score equivalence.
- Built-in classical
Query & Target FASTA
|
[ PaddedSeq ] (Sentinel-padded 64-bit word loads)
|
[ Wavefront Progression s = 0, 1, 2, ... ]
- M_s[k], I_s[k], D_s[k]
- Branchless 64-bit LCP Extension
|
Target Diagonal k = (t_len - q_len) reached with offset >= q_len
|
[ Optimal CIGAR Backtrace ]
|
CIGAR String & Alignment Verification
cargo build --release
cargo test --releasemake test # Runs unit tests or standalone verification suite
make all # Builds release binary# Basic WFA alignment
cargo run --release -- -q data/sample_query.fa -t data/sample_target.fa -m wfa -s
# Classical Gotoh DP mode for verification
cargo run --release -- -q data/sample_query.fa -t data/sample_target.fa -m dp
# Custom affine gap parameters (X=4, O=6, E=2)
cargo run --release -- -q query.fa -t target.fa -x 4 -o 6 -e 2Run automated verification:
./scripts/test_example.sh
./scripts/benchmark_compare.sh| Sequence Length | WFA Latency | Gotoh DP Latency | Speedup | Score Match |
|---|---|---|---|---|
| 200 bp | 0.08 ms | 12.96 ms | 164.3× | 100% Exact (16 == 16) |
| 500 bp | 0.43 ms | 103.72 ms | 242.0× | 100% Exact (40 == 40) |
| 1,000 bp | 3.02 ms | 454.94 ms | 150.6× | 100% Exact (80 == 80) |
MIT License. Copyright (c) 2026 Andreas Sagen.