Block Aligner: an adaptive SIMD-accelerated aligner for sequences and position-specific scoring matrices.

ABSTRACT:

Motivation

Efficiently aligning sequences is a fundamental problem in bioinformatics. Many recent algorithms for computing alignments through Smith-Waterman-Gotoh dynamic programming (DP) exploit Single Instruction Multiple Data (SIMD) operations on modern CPUs for speed. However, these advances have largely ignored difficulties associated with efficiently handling complex scoring matrices or large gaps (insertions or deletions).

Results

We propose a new SIMD-accelerated algorithm called Block Aligner for aligning nucleotide and protein sequences against other sequences or position-specific scoring matrices. We introduce a new paradigm that uses blocks in the DP matrix that greedily shift, grow, and shrink. This approach allows regions of the DP matrix to be adaptively compu

SUBMITTER: Liu D 

PROVIDER: S-EPMC10457662 | biostudies-literature | 2023 Aug

REPOSITORIES: biostudies-literature