Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sequence Alignment and Dynamic Programming

  1. Oct 4, 2011 #1
    1. The problem statement, all variables and given/known data

    I'm having trouble understanding dynamic programming as it relates to sequence alignments. I understand from my lecture notes that the scoring matrix used has arbitrary values (in our case +5 for match, -2 for mismatch, and -6 for gap). I therefore understand why square (1,1) in our lecture notes is assigned a score of +5. However, beyond that I have no idea where the numbers in the scoring matrix came from, how to calculate them, etc. I also don't understand how the algorithm knows whether, in a case of non-matching sequence, to assign a mismatch or gap without first seeing the rest of the sequence. I'd really appreciate it if someone could help me figure this out.

    2. Relevant equations

    Lecture notes:

    http://i3.photobucket.com/albums/y76/Danja91/Dynamic Programming/dynamicprogramming002.jpg

    http://i3.photobucket.com/albums/y76/Danja91/Dynamic Programming/dynamicprogramming001.jpg

    Web site which seems to explain the rules, but I still don't understand them:


    3. The attempt at a solution

    None, really. I found the web site, but I still don't get where the numbers are coming from. I kind of got the following:

    When assigning a score to a square, it is the maximum of the three squares above, to the left, and diagonal-above-left to the square in question. Left takes priority over above, and above takes priority over diagonal.

    I have no idea what the following line means (from the web site)
    You fill in the empty cell with the maximum of these three numbers:
    V3 + 1 if C1 equals C2, or V3 if C1 is not equal to C2, where C1 is the character above the current cell and C2 is the character to the left of the current cell"

    Conceptually I get it, but I don't see how it applies to the matrix presented in my lecture notes.

    Once again, I would appreciate any help. I haven't been this lost in a while.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?