Interactive demo for Smith-Waterman algorithm for simple scoring functions

This was adapted from https://github.com/drdrsh/Needleman-Wunsch by Chris Lockhart for GMU course BINF 401. It solves Smith-Waterman using for simple scoring functions.

See also:

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

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 match/mismatch score, (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.