Effect of changing scoring functions on Optimal alignment ?

Question

[mamai]

My scoring function is as follows:

• Match: 4
• Mismatch: -6
• Gap: -4

This scoring function gives me an optimal alignment if I use global alignment by dynamic programming. I wanted to know if it will will still give me an optimal alignment if I multiply Match, Mismatch and Gap by 1.5?

Answer 1

[Istvan Albert]

Dynamic programming ensures that you always get the optimal alignment that corresponds to a certain scoring function. So regardless of what scores you are using you'll always get the optimal alignment for that scoring.

What you might be asking is whether certain ways of changing the score will always produce the same optimal alignment. The alignment process works by building a matrix where each cell contains the score and the optimal paths are computed by summing these scores and ranking them.

http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

Now operations that can be factored out of the matrix will not alter the ranking, because it will affect all paths identically. Multiplying all scores by a constant is one such case.

[mamai]

Thank you so much for answering. One stupid doubt! So what if we add 1.5 rather than multiplying with Match,Mismatch and Gap. I think it will alter the ranking in that case?

Answer 2

[Rob]

Hi mamai. To answer your question, take a look at slide 26 here. The answer to your question is that multiplying by a positive constant will not change the optimal alignment. The answer to your second question is that for a positive constant k, adding k to the substitution scores and k/2 to the gap scores will not change the optimal alignment. So, in your case, if you add 1.5 to the match and mismatch values and 0.75 to the gap value, this should not affect the optimal alignment.