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 opt score?

once I prove that, I just use Hirschberg from $(i^*, j^*)$ to $(i', j')$ and I'm done.




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy