WFA

WFA performs fast gap-affine pairwise sequence alignment using the wavefront alignment algorithm to accelerate alignments for genomic sequencing data.

Key Features:

• Gap-affine pairwise alignment: Implements an exact gap-affine pairwise sequence alignment algorithm.
• Leverages homologous regions: Exploits homologous regions between sequences to accelerate the alignment process.
• Time complexity: Achieves O(ns) runtime, where n represents the read length and s denotes the alignment score.
• Memory complexity: Uses O(s^2) memory.
• Data dependencies and vectorization: Has simple data dependencies that facilitate vectorization across computing architectures and automatic compiler optimization.
• Empirical performance: Reports 20–300× speedups for short Illumina-like sequences and 10–100× speedups for long noisy reads such as those from Oxford Nanopore compared to other implementations.

Scientific Applications:

• Short-read alignment (Illumina-like): Rapid alignment of short Illumina-like sequencing reads with large speed improvements over other methods.
• Long-read alignment (Oxford Nanopore): Accelerated alignment of long noisy reads produced by technologies such as Oxford Nanopore.
• High-throughput genomic and molecular biology studies: Enables rapid and accurate pairwise alignments in high-throughput sequencing contexts that demand increased throughput and longer read handling.

Methodology:

Implements the wavefront alignment algorithm as an exact gap-affine pairwise method that leverages homologous regions, attains O(ns) runtime (n = read length, s = alignment score) and O(s^2) memory, and relies on simple data dependencies to enable vectorization and compiler optimizations.