Dynamic Programming (DNA sequence alignment)

e.g. ‘a’ vs. ‘s’

•“zasha” vs. “ashes”. 2 possibilities for last letters:

–(1) match ‘a’ with ‘_’:

•best_alignment(“zash”,”ashes”)+1

–(2) match ‘s’ with ‘_’:

•best_alignment(“zasha”,”ashe”)+1

•à best_alignment(“zasha”,”ashes”)

=min(best_alignment(“zash”,”ashes”)+1,

best_alignment(“zasha”,”ashe”)+1)