This is a test version of Biostars. For the public version, visit https://www.biostars.org.
Can pairwise global alignment be done in linear memory with affine gap penalties?

Implementing Needleman-Wunch with affine gap penalties (Gotoh algorithm?) is quite straightforward. However, memory usage grows quadratically with sequence length. Hirschberg's algorithm reduces the growth in memory to linear but I can't see any way to get affine gap penalties to work with this. Is it possible, or must gap penalties be linear if memory usage is also linear?

alignment
• 3,394 views • link
updated by Rob Rob • written by mjlumpe • mjlumpe

1 answer

Yup; it's possible. See, for example, this paper by Myers and Miller.

• 1 views • link
updated by Ram Ram • written by Rob Rob

Log in to answer this question.

More posts like this