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

Browse other questions tagged or ask your own question.