Question: Greedy/Progressive Multiple Alignment
3
gravatar for Erik
6.6 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.5k views
ADD COMMENTlink modified 6.2 years ago by Mdeng510 • written 6.6 years ago by Erik30

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

ADD REPLYlink written 6.6 years ago by Iain260

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

ADD REPLYlink written 6.5 years ago by Niek De Klein2.4k

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

ADD REPLYlink written 6.5 years ago by Niek De Klein2.4k
0
gravatar for Erik
6.6 years ago by
Erik30
Erik30 wrote:

I think I've already figured out points number 2 and 3. Could you please help me with point number 1?

ADD COMMENTlink written 6.6 years ago by Erik30
0
gravatar for Mdeng
6.6 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.

ADD COMMENTlink modified 6.6 years ago • written 6.6 years ago by Mdeng510
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 913 users visited in the last hour