Needleman-Wunsch

This is a demonstration of the Needleman-Wunsch alignment algorithm, invented in 1970 and still strikingly smart.
The implementation was inspired by the example found in the third edition of Numerical Recipes.

Enter any two strings. Most fun if they have some similarity.

Matrix

In the matrix above, start at the top left. Red marks the path, a downwards move means 'pick a character from string A, not from B', a move to the right 'pick a character from string B, not from A'. A diagonal move means pick a character from both. If the characters match, this lowers the penalty by a point. If they don't match we do get a penalty.

The path is picked by starting at the bottom right, and finding the way back to the top left with the least penalties.