Question: Can pairwise global alignment be done in linear memory with affine gap penalties?
0
gravatar for mjlumpe
3.8 years ago by
mjlumpe0
mjlumpe0 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?

alignment • 1.6k views
ADD COMMENTlink modified 3.8 years ago by Rob3.6k • written 3.8 years ago by mjlumpe0
2
gravatar for Rob
3.8 years ago by
Rob3.6k
United States
Rob3.6k wrote:

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

ADD COMMENTlink written 3.8 years ago by Rob3.6k

Excellent, thank you.

ADD REPLYlink written 3.8 years ago by mjlumpe0
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 2836 users visited in the last hour