Provided by: Institute of Electrical & Electronic Engineers
Date Added: Sep 2009
Based on Dynamic Programming (DP), the S-W algorithm is a method that finds an optimal local sequence alignment (i.e., identifying common regions in sequences that share local similarity characteristics) between two DNA or protein sequences (the target sequence and the search sequence). In this paper, the authors present an efficient and high performance linear Recursive Variable Expansion (RVE) implementation of the Smith-Waterman (S-W) algorithm and compare it with a traditional linear systolic array implementation. The results demonstrate that the linear RVE implementation performs up to 2.33 times better than the traditional linear systolic array implementation, at the cost of utilizing 2 times more resources.