Levenshtein Distance

If the following values are considered:

• Sub(a,a) = 0 for ;
• Sub(a,b) = 1 for and ;
• Del(a) = Ins(a) = 1 for .

Then T[m-1,n-1] represents the Levenshtein distance ([10]) between x and y.

Example :
x = YHCQPGK and y = LAHYQQKPGKA

This gives the six following alignments:

which correspond to the six minimum cost paths between (-1,-1) and (6,10):

e-mails: {Christian.Charras, Thierry.Lecroq}@laposte.net