Local alignment linear space

Question

[mitchez]

Hallo,

I am facing a very classical bioinformatic issue: I want to get the best local alignment of two sequences. I know that there are dozens of tools available which do this job in a second but I would like to understand how to solve this problem with only linear amount of space, similar to the Hirschberg algorithm for global sequence alignment https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm. However, the local alignment aligns only a subsequence.

Do you know any literature?

Thanks and best regards,
Mike

Answer 1

[Brian Bushnell]

Try looking for "banded Smith-Waterman". The exact same approach mentioned in your link (only saving 2 lines of information at a given time) can be applied to Smith-Waterman, which is only trivially different from Needleman-Wunsch. Also making it banded allows you to do everything in O(1) extra space rather than linear extra space.