Question: Can pairwise global alignment be done in linear memory with affine gap penalties?
0
gravatar for mjlumpe
4.7 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.8k views
ADD COMMENTlink modified 4.7 years ago by Rob4.2k • written 4.7 years ago by mjlumpe0
2
gravatar for Rob
4.7 years ago by
Rob4.2k
United States
Rob4.2k wrote:

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

ADD COMMENTlink modified 9 months ago by RamRS30k • written 4.7 years ago by Rob4.2k

Excellent, thank you.

ADD REPLYlink written 4.7 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: 1683 users visited in the last hour