Question: objective function of the needleman-wunsch algorithm
1
gravatar for lait
4.0 years ago by
lait130
lait130 wrote:

I am trying to understand what an objective function really is. Every sequence alignment method should have an objective function. When it comes to the needleman-wunsch algorithm, what is precisely the objective function? I know there is a dynamic-programming matrix that should be filled. At each cell (i,j) in the matrix, the value is the maximum of three things: value in cell (i,j-1) - gap penalty, value in cell (i-1,j) -gap penalty, value in cell (i-1,j-1)+substitution score. Is this what is called the objective function ?

ADD COMMENTlink modified 4.0 years ago by Devon Ryan89k • written 4.0 years ago by lait130
1

Yes. because it is a DP algorithm, the function seeks to maximize the alignment score at each position by taking the best choice given the context. Smith Waterman does the same but does not mind loss of information at certain stages, leading to a partial match.

ADD REPLYlink written 4.0 years ago by RamRS21k
2
gravatar for Devon Ryan
4.0 years ago by
Devon Ryan89k
Freiburg, Germany
Devon Ryan89k wrote:

I would consider the objective function to be the resulting scores of the paths through the dynamic-programming matrix. This is what's actually being optimized, after all. That also nicely matches the definition of an objective function, since each path score represents multiple comparison events summarized in a single real value.
 

ADD COMMENTlink written 4.0 years ago by Devon Ryan89k
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: 1732 users visited in the last hour