We are here intererested in finding an optimal alignment between a part of x and a part of y.
The notion of distance is not suitable anymore to get the result thus we have to use the notion of similarity.
We use the following recurrence formula ([18]):
where substitutions, deletions and insertions are given negative values.
To find an optimal local alignment, it is sufficient to find the largest value in the table T and to trace back the path from the square containing this value.
Example :
x = YHCQPGK,
y = LAHYQQKPGKA,
Sub(a,a) = 1,
Sub(a,b) = -3,
Del(a) = Ins(a) = -1.
PGK corresponds to the highest area of similarity between YWCQPGK and LAWYQQKPGKA.