Question: Greedy/Progressive Multiple Alignment
3
7.4 years ago by
Erik30
Erik30 wrote:

I've started learning some algorithms for solving the multiple alignment problem, but there are still things not clear for me in the greedy and progressive methods and I still couldn't find the answer.

1. In the greedy algorithm, I understood that the score for the pairwise alignments is = Matches - Gaps, but when forming the consensus what is the strategy? For example on this case:

GATATT-

G-TCTGA

consensus: GATCTG

Do we have to always choose a letter until we get a consensus sequence of the same size of the starting ones? Because we started by choosing A instead of the gap, but in the end we didn't put an A.

2. And now imagine that I've already aligned the two most similar sequences. When putting the third one, do I have to align it with the consensus sequence from the other two and add gaps as necessary, like in progressive alignment?

3. So apart from how we calculate similarity and the guide tree, the big difference between greedy and progressive algorithms is how we get the final consensus? Because on the progressive algorithm, although we have to be forming the consensus along the alignment process, the final one will be based on a profile.

Thank you.

alignment multiple dna • 2.8k views
modified 6.9 years ago by Mdeng510 • written 7.4 years ago by Erik30

What do you mean by "greedy algorithm"?http://en.wikipedia.org/wiki/Greedy_algorithm

I never heard getting a consensus out of a pairwise alignment, seems kind of pointless to me

I never heard getting a consensus out of a pairwise alignment, why would you want to get this?

0
7.4 years ago by
Erik30
Erik30 wrote:

0
7.3 years ago by
Mdeng510
Germany
Mdeng510 wrote:

1: Consensus is defined as most common letter in a row / raito. Gaps , in a consensus (or profile), would not make sense - because then you could leave them out. And yes, in the result of the multiple alignment process all sequences have the same length.

2: You mean for greedy? You can do booth: align "C" to "A,B" (already aligned) or align "C" to the profile of "A,B" and/or also maybe rate them using the consensus.

3: I don't get it, sorry.