Richard Barnes

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2020-152

August 13, 2020

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-152.pdf

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.

Advisors: Katherine A. Yelick

---

BibTeX citation:

@mastersthesis{Barnes:EECS-2020-152,
    Author= {Barnes, Richard},
    Title= {A Review of the Smith-Waterman GPU Landscape},
    School= {EECS Department, University of California, Berkeley},
    Year= {2020},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-152.html},
    Number= {UCB/EECS-2020-152},
    Abstract= {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.},
}

EndNote citation:

%0 Thesis
%A Barnes, Richard 
%T A Review of the Smith-Waterman GPU Landscape
%I EECS Department, University of California, Berkeley
%D 2020
%8 August 13
%@ UCB/EECS-2020-152
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-152.html
%F Barnes:EECS-2020-152