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...

WFA groups semi-global/overlap/extension into 'ends free', which makes sense to me. (In fact I should add that to the fig somehow.) Wasn't aware that semi-global is also used fo the general thing. I replaced {global-ext, ext} by {ext, local-ext}, since the global one makes more sense / is simpler.

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.

Ohhh, tell me more about clipping penalties! I think that's exactly what I'm trying to formalize more in the semi-global chapter, and I haven't really seen any formal treatment of this so far. Like, one idea (that's easy and I already implemented) is to replace free ends by eg cost-0.5-per-char 1/

I don't unfortunately :( I ran into while looking at the rust bio aligner, that allows for configuring a clipping cost: github.com/rust-bio/rus... Digging back in time it comes from a commit called Smith-Waterman with clipping penalties

github.com/rust-bio/rus... Illumina SW also uses the clipping terminology, but I'm not seeing any other references out there use it. support-docs.illumina.com/SW/DRAGEN_v3...

It seems that clipping is something everyone does, but nobody cares to elaborate and define it properly. I always assumed clipping was a cost-per-char, but it seems to rather be a fixed cost. Is there a max clipping length? What does minimap do? Someone lift the taboo?