SEQanswers

Go Back   SEQanswers > Bioinformatics > Bioinformatics



Similar Threads
Thread Thread Starter Forum Replies Last Post
ChIP-Seq: Comparison of Four ChIP-Seq Analytical Algorithms Using Rice Endosperm H3K2 Newsbot! Literature Watch 0 10-11-2011 04:10 AM
DNA Alignmet Algorithms- Online Alignment Tools kursuni Bioinformatics 2 10-05-2011 05:14 AM
Comparison of alignment tools genbio64 Bioinformatics 6 07-18-2011 10:57 AM
A survey of sequence alignment algorithms for next-generation sequencing nilshomer Literature Watch 4 10-25-2010 07:36 AM
Alignment programs comparison bioxyz Bioinformatics 0 11-25-2009 03:33 PM

Reply
 
Thread Tools
Old 04-04-2011, 11:46 PM   #1
rboettcher
Member
 
Location: Berlin

Join Date: Oct 2010
Posts: 71
Default Comparison of alignment algorithms

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
rboettcher is offline   Reply With Quote
Old 04-05-2011, 08:30 AM   #2
nilshomer
Nils Homer
 
nilshomer's Avatar
 
Location: Boston, MA, USA

Join Date: Nov 2008
Posts: 1,285
Default

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).
nilshomer is offline   Reply With Quote
Old 04-05-2011, 10:24 PM   #3
rboettcher
Member
 
Location: Berlin

Join Date: Oct 2010
Posts: 71
Default

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
rboettcher is offline   Reply With Quote
Old 04-05-2011, 11:54 PM   #4
areyes
Senior Member
 
Location: Heidelberg

Join Date: Aug 2010
Posts: 165
Default

Quote:
Originally Posted by rboettcher View Post
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?
areyes is offline   Reply With Quote
Old 04-06-2011, 12:10 AM   #5
rboettcher
Member
 
Location: Berlin

Join Date: Oct 2010
Posts: 71
Default

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

Last edited by rboettcher; 04-06-2011 at 12:13 AM.
rboettcher is offline   Reply With Quote
Old 04-11-2011, 01:04 AM   #6
jkbonfield
Senior Member
 
Location: Cambridge, UK

Join Date: Jul 2008
Posts: 146
Default

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.
jkbonfield is offline   Reply With Quote
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off




All times are GMT -8. The time now is 12:34 PM.


Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Single Sign On provided by vBSSO