Performance Improvement of the Smith-Waterman Algorithm

Abstract: Efficient sequence alignment is one of the most important and challenging activities in bioinformatics. Many algorithms have been proposed to perform and accelerate sequence alignment activities. Among them Smith-Waterman (S-W) is the most sensitive (accurate) algorithm, however, the fact that it is the most computationally intensive algorithm makes it necessary to implement hardware acceleration methods to make the algorithm viable for practical applications. In this paper, we present a novel approach to improve the performance of the S-W algorithm, using partially custom hardware. In this approach, customized hardware is used to accelerate the computationally intensive part of the algorithm, rather than implementing the entire algorithm in hardware. The paper shows the profiling results of a pure software implementation of the S-W algorithm. The profiling results identify that a specific small part of the algorithm consumes a disproportionately large amount of computational time, amounting to 72.33 % of the total runtime. The paper then shows that implementing this part in hardware, results in a 35.82 times speedup relative to its software equivalent