Optimizing Parallel Scan Smith Waterman Algorithm on GPU

Abstract

Smith-Waterman is a well-known local sequence alignment algorithm that is used for finding regions of maximum similarity between two biological sequences and is known to be a highly compute intensive task. As it is based on dynamic programming it guarantees optimal results. But Dynamic Programming has its own drawbacks such as heavy memory consumption and significant amount of computations. Many academicians and researchers have tried variety of methods to harness the large amount of computational capabilities provided by the GPU in order to make this algorithm run faster. This paper proposes a version of Parallel Scan Smith-Waterman algorithm to improve performance of its phase-2. Here, we have also compared and evaluated performance of proposed work with other approaches like anti-diagonal and blocked anti-diagonal for both constant gap model and affine gap model and have observed remarkable performance gain.