Question: Can pairwise global alignment be done in linear memory with affine gap penalties?

0

mjlumpe •

**0**wrote: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?