Can pairwise global alignment be done in linear memory with affine gap penalties?
1
0
Entering edit mode
5.9 years ago
mjlumpe • 0

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 • 2.1k views
ADD COMMENT
2
Entering edit mode
5.9 years ago
Rob 5.0k

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

ADD COMMENT
0
Entering edit mode

Excellent, thank you.

ADD REPLY

Login before adding your answer.

Traffic: 2560 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6