PDF

Description

A key step in the assembly of genomes is the identification of locally optimal alignments between small subsections of the genome. The Smith-Waterman algorithm provides an exact solution to this problem at the cost of significantly greater computation versus approximate methods. The need to advance both the speed and sensitivity of local alignment has driven a great deal of research on accelerating the Smith-Waterman algorithm using GPUs, which we review here. We find that some optimization techniques are widespread and clearly beneficial, while others are not yet well-explored. We also identify a limited set of algorithmic motifs which can be used to classify all of the existing Smith-Waterman GPU implementations. This exposes gaps in the literature which can be filled through future research.

Details

Files

Statistics

from
to
Export
Download Full History