TSTA: thread and SIMD-based trapezoidal pairwise/multiple sequence-alignment method

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Advancements in DNA sequencing generate large datasets, requiring efficient sequence alignment.
• The Needleman-Wunsch algorithm provides global sequence alignment but is computationally intensive.
• Existing methods struggle to keep pace with the increasing length and volume of sequencing data.

Purpose of the Study:

• To develop a more efficient algorithm for sequence alignment.
• To address the computational bottleneck of traditional dynamic programming methods.
• To accelerate both pairwise and multiple sequence alignment tasks.

Main Methods:

• The study proposes the TSTA algorithm, which utilizes both vector-level and thread-level parallelism.
• The algorithm is designed to optimize the dynamic programming matrix calculation.
• Implementation details and performance benchmarks are discussed.

Main Results:

• The TSTA algorithm demonstrates significant speedups in sequence alignment tasks compared to existing methods.
• Parallelism effectively reduces the computational time for aligning long sequences.
• The algorithm shows scalability for both pairwise and multiple sequence alignment.

Conclusions:

• The TSTA algorithm offers a substantial improvement in efficiency for sequence alignment.
• Leveraging parallelism is crucial for handling large-scale genomic data.
• The developed algorithm provides a valuable tool for modern bioinformatics research.