John Houle
A biologically-significant molecular sequence alignment problem was to find a pair of subsequences of two molecular sequences that had the highest-scoring alignment. The objective was to locate the subsequences of consecutive elements. Any such subsequence of a sequence x1 x2 x3 … xn had the form xi xi+1 xi+2 … xi+k for some 1 ≤ i ≤ n and k ≤ n – i. The problem of finding the highly-related subsequences of two molecular sequences was formally defined as the local alignment problem. The Smith-Waterman algorithm solved the local alignment problem for two molecular sequences using a dynamic programming algorithm. The Smith-Waterman algorithm was reviewed. The review surveyed nine topics: 1. local alignment problem, 2. Smith-Waterman algorithm, 3. Smith-Waterman algorithm complexity analysis, 4. amino acid substitution matrices, 5. Smith-Waterman algorithm example computation, 6. Smith-Waterman algorithm extensions, 7. heuristic alignment algorithms, 8. performance analysis and 9. hardware technologies. The review concluded with a prediction of future research directions in Smith-Waterman algorithm research.