Variations on dynamic programming

d(i,j)= min

{

d(i-1,j)+ g

d(i,j-1)+ g

d(i-1,j-1) + t(vi,wj)

t(vi,wj) = m if vi=wj

t(vi,wj) = n if vi ? wj

g - gap penalty (e.g. 2)

m - match score (e.g. -1)

n - mismatch score (e.g.+1)

(In practice signs are reversed and the max is taken, and the highest overall score is the most significant )

Previous slide

Next slide

Back to first slide

View graphic version