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

Question

[mjlumpe]

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?

Answer 1

[Rob]

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

[mjlumpe]

Excellent, thank you.