Smith-Waterman Algorithm

The Smith-Waterman algorithm performs local sequence alignment, determining similar regions between two strings of nucleic acid or protein sequences by comparing segments of all possible lengths rather than the entire sequence and optimizing the similarity measure. It was first proposed by Temple F. Smith and Michael S. Waterman in 1981. Like the Needleman-Wunsch algorithm, of which it is a variation, Smith-Waterman is a dynamic programming algorithm guaranteed to find the optimal local alignment for the scoring system used; its main difference from Needleman-Wunsch is that negative scoring matrix cells are set to zero, with the traceback procedure starting at the highest-scoring cell and continuing until a cell with a score of zero is reached. Because of its quadratic time complexity it is often replaced in large-scale problems by more computationally efficient alternatives.