Smith-Waterman / Needleman-Wunsch dynamic programming

Needleman-Wunsch 1970 (global) and Smith-Waterman 1981 (local) dynamic-programming alignment with score recurrence H(i,j) = max{H(i-1,j-1)+s, H(i-1,j)-d, H(i,j-1)-d, 0}. O(mn) time and space; exact-optimal under affine-gap scoring. …