Accel-Align: a fast sequence mapper and aligner based on the seed-embed-extend method.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomic Data Analysis

Background:

• Sequencing technology advancements are reducing costs, but mapping genomic data remains computationally intensive due to reliance on edit distance for INDELs and mismatches.
• Current sequence mappers use seed-filter-extend methods with filtration heuristics, which have inherent performance-accuracy trade-offs limiting their effectiveness.

Purpose of the Study:

• To introduce a novel methodology, SEE (Sequence Embedding and Estimation), for developing efficient sequence mappers and aligners.
• To shift the focus from eliminating sub-optimal candidates to identifying optimal candidates in sequence alignment.

Main Methods:

• SEE transforms sequence strings from the edit distance regime to the Hamming regime using randomized low-distortion embedding.
• Hamming distance is computed on the embedded sequences to efficiently identify optimal alignment candidates.
• Accel-Align, an SEE-based short-read mapper, was developed to demonstrate practical application.

Main Results:

• Accel-Align demonstrates a 3-12x speed improvement over state-of-the-art aligners on commodity CPUs.
• The SEE methodology achieves comparable accuracy to existing methods without requiring specialized hardware.
• SEE offers a significant performance enhancement for short-read sequence mapping and alignment.

Conclusions:

• Randomized embeddings offer new optimization pathways for sequence alignment beyond traditional edit distance calculations.
• The SEE methodology has broad applicability, including graph alignment, multiple sequence alignment, and sequence assembly.
• This approach is well-suited for future sequencing technologies with increasing read lengths and throughput.