Comparison of alignment algorithms

[rboettcher]

Hi all,
I was wondering how the different algorithms for optimal alignments (NW, SW etc.) compare to each other in terms of runtime, since I've been told that NW and SW are very ineffective/slow, but Hirschberg and Gotoh only offer minor improvements (if any).
So far I've found differing statements concerning complexity and runtime...

My main focus lies on runtime, though memory requirements are of course to be considered as well if there are very great differences.
I hope that somebody can detangle the whole subject for me, especially in terms of linear and affine gap costs.
Oh and please don't tell me to use public available aligners like bowtie or BWA instead (I already do that btw), because this is absolutely NOT helping with my project at university

Thank you in advance and have a nice day

[nilshomer]

Ah, so this is for homework, so should we really be helping?

Did you know that all these algorithms can be made to work in a linear amount of memory (think Frontier search)? Their time complexities are well described their respective papers, so I am not sure how they are differing.

Linear vs. Affine really comes down to finding longer gaps, and what are the relative scoring penalties (gap open/extend vs. mismatch/match).

[rboettcher]

Thehe, since the goal is to implement a fast aligner, I was hoping you could give me a push in the right direction in terms of which algorithm to chose
For example, I read that Hirschberg algorithm is a little slower than NW but way more efficient concerning memory, but this is just slightly indicated by the complexity mentioned (if it is mentioned at all, I'm not sure right now).
That is why I would like to have a ranking or a table that tells me which of the algorithms is the fastest/best in terms of runtime and memory consumption (I think this might be handy for other people as well).
I already tried to find something like that, but I didn't succeed so far (will continue searching though).

Regards

[areyes]

Hi all,
Oh and please don't tell me to use public available aligners like bowtie or BWA instead (I already do that btw), because this is absolutely NOT helping with my project at university

Sorry for not having an answer for your question. But your phrase called my attention, why is this so?

[rboettcher]

It does not help because I was told to implement a pairwise sequence alignment which is time dependent and very accurate
I tried to get some inspiration from the commonly used software, but until now it is a little to advanced for me...
Moreover it has to be finished soon, that is why I'm searching for help.
We're also using common aligners for getting used to the handling, still I'm obliged to implement some algorithm using a dynamic programming approach for reasons of understanding the whole process (and as programming exercise).
If you think it's a waste of time feel free to contact my professor

Regards

[jkbonfield]

The hirschberg (or Gotoh's?) technique, if I recall, pretty much involves in recursively breaking the alignment down into smaller bits. However to find an appropriate point on the alignment matrix to split at it has to run the alignment through anyway, albeit without storing data, so it essentially does double the work in order to use far less memory. I may be wrong on that though as it's been a long time!

I'd advise checking some of the earlier linear space alignment algorithms from Miller and Myers. They're pretty hard to follow due to excessive use of single letter variables, but they're a goof starting point for full local and global alignment calculations. See http://bioinformatics.oxfordjournals...t/4/1/11.short. They later did a variant that uses a band to avoid the full N^2 complexity, and later still some block stiching version.

Modern techniques tend to use hashing more though - looking for exact matching "words" of sequence and then either stitching these together to produce an actual alignment or using the location of the words to control a band through the alignment matrix.