Sequence Alignment Revisited
Problem1 Sequence Alignment
We can reduce the space by using only two column instead.
Space-Efficient-Alignment(X ,Y)
Array B[0…m,0…1] Initialize B[i,0]=iδ for each i (just as in column 0 of A) For j=1,…,n B[0,1]=j$\delta$ (since this corresponds to entry A[0,j]) For i=1,…,m B[i, 1]= min[$\alpha x_iy_j$ + B[i − 1, 0], $\delta$ + B[i−1,1], $\delta$ + B[i,0]] Endfor Move column 1 of B to column 0 to make room for next iteration: Update B[i, 0]= B[i, 1] for each i Endfor However, this doesn’t left enough information to get back the information about alignment.……