Fast noisy long read alignment with multi-level parallelism.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Second-generation sequencing has limitations like short read lengths and PCR biases.
• Single Molecule Real-Time (SMRT) sequencing offers longer reads but generates large data volumes and has high error rates.
• Existing alignment tools struggle with SMRT data due to read length, error rates, and single CPU performance bottlenecks.

Purpose of the Study:

• To develop an efficient parallel alignment algorithm for noisy long reads generated by SMRT sequencing.
• To address the computational challenges posed by increased data volume and error rates in SMRT data.
• To overcome the performance limitations of single CPUs for sequence alignment.

Main Methods:

• Introduction of ParaHAT, a parallel alignment algorithm incorporating vector-level, thread-level, process-level, and heterogeneous parallelism.
• Redesign of dynamic programming matrices to eliminate data dependency, enabling effective vectorization for base-level alignment.
• Implementation using Message Passing Interface (MPI) for multi-node computing and heterogeneous parallel technology for enhanced speed.

Main Results:

• ParaHAT achieves a 10.03x speedup in base-level alignment compared to existing methods.
• Demonstrates high parallel acceleration ratio (94.61%) and weak scalability (98.98%) on 128 nodes.
• Effectively handles noisy long reads and overcomes computational limits of single-node processing.

Conclusions:

• ParaHAT provides a scalable and efficient solution for aligning noisy long reads from SMRT sequencing.
• The parallel architecture significantly enhances alignment speed and throughput.
• ParaHAT overcomes key computational bottlenecks, making SMRT data analysis more feasible.