Post

New set of thesis figures on pairwise alignment just dropped! - schematic and worked example for many algorithms - alignment modes

And some more: - edit graph - cubic DP (as N&W originally introduced it) + quadratic DP (as fixed by many others) - cost models

See them in action here :) Although I may have to split the large ones so they go part-by-part. curiouscoding.nl/posts/pairwi...

It's been very cool to watch the content on your site grow. I've been dabbling with some alignment adjacent things and your posts have been invaluable.

Question on semi-global alignment - where did you find / come up with the names of "overlap", "extension", etc? I'd always thought of all of those as just variants of semi-global.

My basis for what is semi-global is coming from only two sources though. This set of slides from @robp.bsky.social rob-p.github.io/CMSC423_S20/... And the source code for parasail.

Asking the right questions there :") The semi-global fig is based on an earlier fig I did with Pesho, but redone to have a consistent style. The names are mostly from the WFA repo, and then I did a bit of freedom on top of that 1/ x.com/peshotrie/st...

I like the 'ends free' term! That feels like a much better descriptor than semi-global. Thanks for the twitter link too, that's helpful to see. I wonder why parasail chose to implement a "dynamic" semi-global instead of implementing all the different specific combinations.

I thought about it a bit more, and actually I think that in practice, ends-free is not actually a catch-all. Rather, it's the case where relatively short ends are free, so that the problem is still sufficiently similar to global alignment.

That feels like a good distinction to have, given the number of algos that do that. It's a discontinuous clipping penalty, kind of. Great addition of the solid bars indicating where start and end is allowed.

Supporting all free end combos seems sub-optimal performance wise.