Accel-Align

Accel-Align maps and aligns sequencing reads to reference genomes using the seed–embed–extend (SEE) methodology to convert edit-distance comparisons into Hamming-distance computations for faster short-read alignment.

Key Features:

• Innovative Methodology: The seed–embed–extend (SEE) approach transforms sequence data from the edit distance regime to the Hamming distance regime using a randomized low-distortion embedding to identify optimal alignment candidates rather than filter suboptimal ones.
• Performance and Accuracy: Reports 3–12× speed improvements over state-of-the-art aligners on commodity CPUs while maintaining comparable alignment accuracy without special-purpose hardware.
• Algorithmic Advances: Uses randomized low-distortion embedding algorithms to handle indels and mismatches and to reduce the computational overhead of edit-distance calculations.
• Broad Applicability: Suited for short-read sequence mapping and alignment and extensible to related tasks such as graph alignment, multiple sequence alignment, and sequence assembly.

Scientific Applications:

• High-throughput short-read mapping: Rapid mapping of high-throughput sequencing reads to reference genomes for large-scale genomic studies and analyses involving increasing read lengths.
• Extended sequence analysis: Application of embedding-based candidate selection to accelerate graph alignment, multiple sequence alignment, and sequence assembly tasks.

Methodology:

The computational workflow follows the SEE process: Seed — identify candidate alignment locations; Embed — apply a randomized low-distortion embedding to convert edit-distance comparisons into Hamming-distance computations; Extend — perform alignment extension and select optimal candidates.