Smith-Waterman Algorithm (cont.)
Only works effectively when gap penalties are used
In example shown
- match = +1
- mismatch = -1/3
- gap = -1+1/3k (k=extent of gap)
Start with all cell values = 0
Looks in subcolumn and subrow shown and in direct diagonal for a score that is the highest when you take alignment score or gap penalty into account
Hij=max{Hi-1, j-1 +s(ai,bj), max{Hi-k,j -Wk}, max{Hi, j-l -Wl}, 0}