BiWFA

BiWFA implements the bidirectional Wavefront Alignment (WFA) algorithm to compute exact gap-affine pairwise sequence alignments with reduced memory usage for large-scale genomic and long-read sequencing data.

Key Features:

• Optimal Gap-Affine Alignment: Computes exact optimal pairwise sequence alignments under a gap-affine scoring model.
• Bidirectional Wavefront Alignment: Implements a bidirectional WFA algorithm to perform wavefront-based alignments.
• Memory Efficiency: Operates in O(s) memory, where s is the optimal alignment score, reducing the O(s²) memory requirement of traditional WFA implementations.
• Time Complexity: Retains a time complexity of O(ns), with n denoting sequence length.
• Practical Performance: Demonstrated alignment of noisy Oxford Nanopore Technologies reads up to 1 Mbp using on the order of a few hundred megabytes of memory.

Scientific Applications:

• Genomics and Bioinformatics: Aligns long sequences from next-generation sequencing technologies for genome-wide analyses and large-scale genomic datasets.
• Comparative Genomics: Enables comparative genomic analyses by providing efficient gap-affine alignments for identifying evolutionary relationships and functional annotations across species.

Methodology:

Uses a bidirectional Wavefront Alignment algorithm and reduces memory usage by optimizing storage and access of intermediate alignment results during the alignment process.