Fast noisy long read alignment with multi-level parallelism.

Authors

Zeyu Xia, Canqun Yang, Chenchen Peng, Yifei Guo, Yufei Guo, Tao Tang, Yingbo Cui

Published in

BMC bioinformatics. Volume 26. Issue 1. Pages 118. May 02, 2025. Epub May 02, 2025.

Abstract

The advent of Single Molecule Real-Time (SMRT) sequencing has overcome many limitations of second-generation sequencing, such as limited read lengths, PCR amplification biases. However, longer reads increase data volume exponentially and high error rates make many existing alignment tools inapplicable. Additionally, a single CPU's performance bottleneck restricts the effectiveness of alignment algorithms for SMRT sequencing.
To address these challenges, we introduce ParaHAT, a parallel alignment algorithm for noisy long reads. ParaHAT utilizes vector-level, thread-level, process-level, and heterogeneous parallelism. We redesign the dynamic programming matrices layouts to eliminate data dependency in the base-level alignment, enabling effective vectorization. We further enhance computational speed through heterogeneous parallel technology and implement the algorithm for multi-node computing using MPI, overcoming the computational limits of a single node.
Performance evaluations show that ParaHAT got a 10.03x speedup in base-level alignment, with a parallel acceleration ratio and weak scalability metric of 94.61 and 98.98% on 128 nodes, respectively.

PMID:
40316905
Bibliographic data and abstract were imported from PubMed on 03 May 2025.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.