Interactive demo for Smith-Waterman algorithm with substitution matrices

This was adapted from https://github.com/drdrsh/Needleman-Wunsch by Chris Lockhart for GMU course BINF 401. It solves Smith-Waterman with amino acid subsitution matrices.

See also:

• Needleman-Wunsch for simple scoring functions
• Needleman-Wunsch with substitution matrices
• Smith-Waterman for simple scoring functions

1. Create a table, and write one sequence along the column and another along the rows with one extra row or column at the beginning
2. Initialize the first row or column with 0s
3. Begin scoring. You can score any cell if the cells diagonal, upper, and left of it have values. You evaluate three scores: (i) The diagonal score plus the score from the substitution matrix, (ii) the upper score plus the gap penalty, and (iii) the left score plus the gap penalty. You take whichever score is greatest, and make a note if that score came from the diagonal, upper, or left cell. If the score is negative, you put a 0 instead.
4. Perform traceback. Start from the cell with the highest score, and work your way backward following the indications where the scores came from until you hit a 0. A diagonal move indicates that you accept the letter in the two sequences, a vertical move indicates that you insert a gap into the sequence along the columns and take the letter from the sequence along the rows, and a horizontal move indicates that you insert a gap into the sequence along the rows and take the letter from the sequence along the columns.