Finding alignment about edlib HOT 7 CLOSED

Finding alignment is not so hard! I know for each block its vertical deltas for every cell and horizontal delta of last cell in block. This means that if I store vertical and horizontal deltas for all blocks, I can reconstruct path of alignment. For each cell on path, I will have to compute part of block it belongs to.
I implemented this, it slows whole algorithm about 3, 4 times and takes a lot of memory.

from edlib.

Interesting: if query is larger then target, then optimal path will not go through so many blocks and finding alignment will be faster! In HW and SHW this does not affect us because we can not swap query and target, but in NW we can so this should be considered. On the other side, in NW query and target will usually be of similar length, so this does not really help

from edlib.

I should speed up alignment, and also make it consume much less memory.
Options I have for that: Hirschbergs algorithm, or something similar to what they did in SSW.
SSW idea could work pretty well for HW and SHW, since query is small there.
For NW I do not believe it will be very useful, so this is where I could consider Hirschberg.

from edlib.

I could also just try to use less space, by doing something smart hm. But big problem is that I do not want to allocate memory too often. I could use something like vector, to allocate memory dinamically?

from edlib.

I implemented SSW idea of finding alignment. SHW and HW now use NW alignment to find alignment. NW alignment is still implemented like before. Next step is to make NW use less memory, or implement it with Hischberg. I did some tests and it seems like Hirschberg method can be much slower in some cases, so I will not try it so soon.

from edlib.

I should change finding of alignment for NW so it uses only space needed for band, not the whole matrix.

from edlib.

I will create new issue for this!

from edlib.