How does the Smith-Waterman algorithm work?
The Smith-Waterman algorithm is searching for homology by comparing sequences. When sequences are compared using local alignments, the total number of alignments can be considerable, and identification of the best alignments is of high importance to both the reliability and relevance of the data obtained. This identification of the optimal local alignment between two sequences is basically what the Smith-Waterman algorithm does. Optimal local alignments are identified by comparing the query sequence and the sequences in the database on a character-to-character level. Contrary to the Needleman-Wunsch algorithm, on which the Smith-Waterman algorithm is built, the Smith-Waterman algorithm is searching for local alignments, not global alignments, considering segments of all possible lengths to optimize the similarity measure [Smith and Waterman, 1981]. The algorithm is based on dynamic programming which is a general technique used for dividing problems into sub-problems and solving these s
