7.5 years ago by

Mountain View, CA

See the introductory slides here. I think you understand how to fill the DP matrix. For each cell in the DP matrix, we pick the max of three directions from three adjacent cells: UP, LEFT, DIAGONAL. UP and LEFT give you one gap, DIAGONAL give you match/mismatch.

Now the affine gap penalty makes the calculation more difficult. For each cell, we still pick the max of the three directions. But now since the gap score is not linear anymore (i.e. `Two gaps != 2 x one gap`

), you'll have to consider all the cells on LEFT, all the cells on UP, rather than just the immediate neighbor.

This also increase the computational complexity from squared to cubic.