rHAT

rHAT aligns noisy long reads from Single Molecule Real-Time (SMRT) sequencing to reference genomes using regional hashing and a seed-and-extension strategy to improve alignment speed and accuracy.

Key Features:

• SMRT long-read optimization: Tailored for noisy long reads produced by Single Molecule Real-Time (SMRT) sequencing to accommodate large read lengths and high error rates.
• Seed-and-Extension Approach: Employs a seed-and-extension strategy specifically adapted for noisy long reads to balance efficiency and accuracy.
• Regional Hash Table (RHT): Uses a Regional Hash Table index that captures short tokens within localized reference windows to rapidly identify potential match sites.
• Efficient Seeding Phase: Computes occurrences of short token matches between partial reads and local genomic windows to identify highly probable candidate alignment sites with minimal overhead.
• Sparse Dynamic Programming Extension: Applies a sparse dynamic programming-based heuristic during extension to reduce computational cost when aligning reads to candidate sites.
• Implementation: Implemented in C++ for computational efficiency.

Scientific Applications:

• SMRT read alignment: Aligns long, noisy SMRT sequencing reads to reference genomes for downstream genomic analyses.
• Prokaryotic and eukaryotic genome studies: Applicable to alignment tasks in both prokaryotic and eukaryotic genomes where large read lengths and high error rates are present.

Methodology:

Builds a Regional Hash Table (RHT) index of short tokens in localized reference windows, performs an efficient seeding phase that computes occurrences of short token matches between partial reads and local genomic windows to identify candidate sites, and uses a sparse dynamic programming-based heuristic for extension to align reads to those candidate sites.