To do Dynamic Programming: First write one sequence across the top, and one down along the side 2 5 Gap V D S 0 Gap -8-16-24 32-40 1y.44-4→12→20→28 2 E 16-67-1 3 S 24-14-6 3222-14 30 40-3022 133 48-3830-15523
1 2 3 4 5 6 To do Dynamic Programming: First write one sequence across the top, and one down along the side i =0 1 2 3 4 5 j = Gap V D S C Y 0 Gap 0 4 -8 -4 -3 -8 -16 -24 -32 -40 -8 V -8 4 -12 -20 -28 E -16 -6 7 2 -1 -9 -17 S -24 -14 1 -7 3 -6 9 L -32 -22 -14 -30 3 0 C -40 -22 -7 1 13 3 Y -48 -38 -30 -15 5 23
The traceback After the alignment square is finished, start at the lower right and work backwards following the arrows to see how you got there 2 5 Gap V D 0 Gap -8-16-24 32-40 2→-20→-28 2 E 16-6751 3 S 24-14-6 3222-14 40-3022 133 483830-15523
The Traceback: After the alignment square is finished, start at the lower right and work backwards following the arrows to see how you got there… i =0 1 2 3 4 5 j = Gap V D S C Y 0 Gap 0 4 -8 -16 -24 -32 -40 1 V -8 2 E -16 3 S -24 4 L -32 5 C -40 6 Y -48 -8 4 -4 -3 -8 -12 -28 -6 -14 -22 -30 -38 7 3 -6 -14 -22 -30 9 2 -1 1 -7 -15 -9 1 3 13 5 -17 -7 0 3 23 -20
The traceback V Y V E Y gives the alignment 2 5 Gap V D s 0 Gap -8-16-24 32-40 2→-20→-28 2 E 16-6751 3 S 24-146 3222-14 5 C 40-3022 3 Life must be lived forwards and understood backwards Soren Kierkegaard
Y -48 1 2 3 4 5 6 -38 -30 -15 5 23 The Traceback V D S – C Y V E S L C Y gives the alignment: i =0 1 2 3 4 5 j = Gap V D S C Y 0 0 -8 -16 -24 -32 -40 -8 Gap V E S L C -8 -16 -24 -32 -40 4 4 -4 -3 -8 -12 -28 -6 -14 -22 -30 7 3 -6 -14 -22 9 2 -1 1 -7 -9 1 3 13 -17 -7 0 3 “Life must be lived forwards and understood backwards.” -20 - Søren Kierkegaard
Local Alignment Temple Smith and Michael Waterman, 1981-modified Needleman-Wunsch-sellers Local alignment is the best scoring alignment of a substring n sequence x to a substring in sequence y. KEY ELEMENT IS NOT TO FORCE THE ALIGNMENT TO GO TO THE ENDS OF THE SEQUENCES For sequence x, residues 1, 2, 3...N, can pick up to-N2 substrings e. start point a= 1, 2 .. n and end point b=1, 2. n. Same for sequence y, - M2substrings. For any two substrings, we have the old o(mn ) alignment problem, so the total number of possible alignments is -N2M2(NMO(MN3 )-UGLY!! ! Solveable in polynomial time, but a big polynomial!!!
Local Alignment • Temple Smith and Michael Waterman, 1981 – modified Needleman-Wunsch-Sellers Local alignment is the best scoring alignment of a substring in sequence x to a substring in sequence y. KEY ELEMENT IS NOT TO FORCE THE ALIGNMENT TO GO TO THE ENDS OF THE SEQUENCES. For sequence x, residues 1, 2, 3…..N, can pick up to ~N2 substrings, i.e. start point a= 1,2….N and end point b= 1, 2….n. Same for sequence y, ~M2 substrings. For any two substrings, we have the old O(mn) alignment problem, so the total number of possible alignments is ~ N 2 M 2(NM)=O(M 3 N 3)- UGLY!!!! Solveable in polynomial time, but a big polynomial!!!
Local Alignment Again, dynamic programming comes to the rescue Same basic scheme for dynamic programming as before except Similarity matrix MUST include negative values for mismatches AND- When the value calculated for a position in the scoring matrix is Negative, the value is set to zero THIS TERMINATES THE ALIGNMENT
Local Alignment • Again, dynamic programming comes to the rescue! Same basic scheme for dynamic programming as before except…. Similarity matrix MUST include negative values for mismatches --AND– ****When the value calculated for a position in the scoring matrix is Negative, the value is set to zero. THIS TERMINATES THE ALIGNMENT