Greedy Algorithms for Pairwise Alignment

1 Algorithm 4 Tool for Aligning Very Similar DNA Sequences [7] 

As the vectors at cost c depend only on those at costs c and c-1, a linear-space version of the above relationship can be derived. 

A linear space version of the recurrence relation can be derived. The psendocode for the linear space algorithm for alignment is as follows  

FIGURE 11.8 Global alignmentof sequences S = uucgauugu and T = cccggguga with a + 1 for a match. 

---