BWT-SW

BWT-SW performs exhaustive local alignment of nucleotide sequences by combining Burrows–Wheeler Transform indexing with dynamic programming–based Smith–Waterman alignment.

Key Features:

• Exhaustive Local Alignment Detection: Identifies all possible local alignments between nucleotide sequences rather than relying on heuristic approximations.
• Burrows–Wheeler Transform Indexing: Uses Burrows–Wheeler Transform (BWT) indexes to efficiently search large genomic sequences such as the human genome.
• Dynamic Programming Integration: Combines BWT indexing with dynamic programming–based Smith–Waterman alignment to accelerate local alignment computation.
• Memory-Efficient Genome Indexing: Stores large genomes, including the ~3 billion base human genome, using approximately 1 gigabyte of memory.
• Genome-Scale Alignment Capability: Aligns long nucleotide patterns, such as sequences of approximately 3,000 nucleotides, against genome-scale references.

Scientific Applications:

• Comprehensive Sequence Alignment: Detects complete sets of local alignments between nucleotide sequences and reference genomes.
• Alignment Validation: Verifies and evaluates alignments generated by heuristic sequence alignment tools such as BLASTn.
• Genome-Scale Similarity Analysis: Enables detection of sequence similarity across large genomic datasets.

Methodology:

BWT-SW constructs Burrows–Wheeler Transform indexes of reference sequences and performs exhaustive Smith–Waterman local alignments through dynamic programming accelerated by BWT-based indexing.