Implementation of the Smith-Waterman algorithm on an FPGA

Abstract

Bioinformatics is a continuously growing research area which merges biology, computational science and information technology to uncover the genetic information hidden in every living species. DNA, the basic molecule of life, directly controls the fundamental biology of any living organism. The variations and errors in the DNA sequence define the tendency of developing diseases or resistance to these diseases. Sequence alignment algorithms, such as the Smith-Waterman algorithm, are used to align genetic sequences resulting in the identification of high similarity regions which may indicate the relationship between the two biological sequences. The Smith-Waterman algorithm generates a similarity matrix in which each cell represents a similarity score between the genetic elements. This dissertation presents a new path reconstruction algorithm which identifies the location of each mutation in the sequences and their type (insertion, deletion or substitution). This algorithm reconstructs the path during the computation of the Smith-Waterman algorithm unlike the traditional algorithm which traces the path after the similarity matrix is constructed. The implementation developed in this dissertation is based on a systolic array architecture made of processing elements which compute a simplification of the Smith-Waterman algorithm commonly known as differential coding. This simplification computes the similarity between two biological elements using one bit and therefore a high degree of speedup is achieved.