according to the Smith-Waterman setup, I have 2 string sequences S and T, and I want to identify their respective subsequences $\alpha$ and $\beta$ whose global alignment have maximum score over all pairs of subsequences. As usual, the scoring system is a substitution matrix and a gap-scoring scheme. However, I want to find $\alpha$ and $\beta$ with linear space.
I know how to find the terminating point $(i^*, j^*)$ of the subsequences - I'm doing
DP (dynamic programming) from the top-left, while throwing away negative scores. The values in each row can be computed in a
row wise fashion and the algorithm must store values for only two rows at a time = linear space. I'll maintain the best score I saw and call it
opt, and the indexes of
opt would be $(i^*, j^*)$.
But now how do I find the starting point $(i', j')$? I thought about doing
DP starting from $(i^*, j^*)$ going to the top-left corner, and stop when I reach the
opt score from before. But how do I prove that I'll find a point with the
once I prove that, I just use
Hirschberg from $(i^*, j^*)$ to $(i', j')$ and I'm done.