Dynamic Programming (DNA sequence alignment)

Pseudocode (bottom-up)

Given: Strings X,Y , Table[0..x,0..y]

For i=1 to x do

Table[i,0]=i

For j=1 to y do

Table[0,j]=i

i=1, j=1

While i<=x and j<=y

If X[x]=Y[y] Then

// matches – no underscores

Table[x,y]=Table[x-1,y-1]

Else

Table[x,y]=min(Table[x-1,y],Table[x,y-1])+1

End If

i=i+1

If i>x Then

i=1

j=j+1

End If