Accelerating the Smith-Waterman algorithm with interpair pruning and band optimization for the all-pairs comparison of base sequences.

ABSTRACT:

Background

The Smith-Waterman algorithm is known to be a more sensitive approach than heuristic algorithms for local sequence alignment algorithms. Despite its sensitivity, a greater time complexity associated with the Smith-Waterman algorithm prevents its application to the all-pairs comparisons of base sequences, which aids in the construction of accurate phylogenetic trees. The aim of this study is to achieve greater acceleration using the Smith-Waterman algorithm (by realizing interpair block pruning and band optimization) compared with that achieved using a previous method that performs intrapair block pruning on graphics processing units (GPUs).

Results

We present an interpair optimization method for the Smith-Waterman algorithm with the aim of accelerating the all-pai

SUBMITTER: Okada D 

PROVIDER: S-EPMC4595212 | biostudies-literature | 2015 Oct

REPOSITORIES: biostudies-literature