Dynamic Programming Worksheet
by Ed Pillsbury and Ranjit Bindra
Part 1:
Fill out identity matrix for hypothetical protein sequencesà
Sequence 1à BNRNLRDOFGYN
Sequence 2à QDRBFNOGFONB
|
B |
N |
R |
N |
L |
R |
D |
O |
F |
G |
Y |
N |
|
|
Q |
||||||||||||
|
D |
||||||||||||
|
R |
||||||||||||
|
B |
||||||||||||
|
F |
||||||||||||
|
N |
||||||||||||
|
O |
||||||||||||
|
G |
||||||||||||
|
F |
||||||||||||
|
O |
||||||||||||
|
N |
||||||||||||
|
B |
Part II:
Fill in Sum Matrix and then shade in the tracebacksà
|
B |
N |
R |
N |
L |
R |
D |
O |
F |
G |
Y |
N |
|
|
Q |
||||||||||||
|
D |
||||||||||||
|
R |
||||||||||||
|
B |
||||||||||||
|
F |
||||||||||||
|
N |
||||||||||||
|
O |
||||||||||||
|
G |
||||||||||||
|
F |
||||||||||||
|
O |
||||||||||||
|
N |
||||||||||||
|
B |
ANSWER KEY:
Part I:
|
B |
N |
R |
N |
L |
R |
D |
O |
F |
G |
Y |
N |
|
|
Q |
||||||||||||
|
D |
1 |
|||||||||||
|
R |
1 |
1 |
||||||||||
|
B |
1 |
|||||||||||
|
F |
1 |
|||||||||||
|
N |
1 |
1 |
1 |
|||||||||
|
O |
1 |
|||||||||||
|
G |
1 |
|||||||||||
|
F |
1 |
|||||||||||
|
O |
1 |
|||||||||||
|
N |
1 |
1 |
1 |
|||||||||
|
B |
1 |
Part II:
|
B |
N |
R |
N |
L |
R |
D |
O |
F |
G |
Y |
N |
|
|
Q |
5 |
5 |
4 |
4 |
4 |
4 |
3 |
3 |
2 |
1 |
1 |
0 |
|
D |
5 |
5 |
4 |
4 |
4 |
3 |
4 |
3 |
2 |
1 |
1 |
0 |
|
R |
5 |
4 |
5 |
3 |
3 |
4 |
3 |
3 |
2 |
1 |
1 |
0 |
|
B |
5 |
4 |
4 |
3 |
3 |
3 |
3 |
3 |
2 |
1 |
1 |
0 |
|
F |
4 |
4 |
4 |
3 |
3 |
3 |
3 |
2 |
3 |
1 |
1 |
0 |
|
N |
3 |
4 |
3 |
4 |
3 |
3 |
3 |
2 |
2 |
1 |
1 |
1 |
|
O |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
2 |
1 |
1 |
0 |
|
G |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
2 |
1 |
0 |
|
F |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
1 |
2 |
1 |
1 |
0 |
|
O |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
1 |
0 |
|
N |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
B |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 optimum alignments (i.e. alternate tracebacks)
B N R N L R D O F G Y -- N --
Q D R B F N -- O -- G F O N B
Or
B N R N L R D O -- F G Y N --
Q D R B F N -- O G F O -- N B
-see if you can find the one mistake in the matrix. (HA HA HA HA!!!)
HINT: think of our initials.