This is a test version of Biostars. For the public version, visit https://www.biostars.org.
Local alignment linear space

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

smith-waterman alignment
• 3,149 views • link
updated by Ram Ram • written by mitchez • mitchez

1 answer

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.

• 0 views • link
updated by Ram Ram • written by Brian Bushnell Brian Bushnell

Log in to answer this question.

More posts like this