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/

by simply alternating edges of cost 0 and 1 along the edges. The ratio of 0 and 1 can also make more fine-grained clipping-costs. This can also replace a fixed cut-off length by just a fixed cost along the *entire* edge. Do you happen to know some papers on this?

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?

I’d always thought of clipping as a post-main alignment step, which I think is how BWA describes it as well? rust-bio is abnormal (to me) for how it describes clipping, which really just sounds like a fixed cost gap open penalty is what they actually mean.

Aside from ends-free (your definition) I do wonder what the real life utility of affine-ends gap scores is though? Like when would you want a different ends cost vs your normal affine-gap scoring

The idea is that you may be mapping 10kb reads onto a many MB genome, but the reads have noisy ends due to ONT sequencing. So you preferably align them fully, but for a cost, you can skip say the last 100 characters. But it's slightly weird to me that this cost is fixed instead of variable.

I haven’t gone back to read the original papers that talk about affine gap penalty, but they must discuss using different cost functions for different gap types?