BSA1
Excercise: Dynamic programming in a spreadsheet
In a dynamic programming matrix a cell is calculated from three
neighboring cells and the same expression is used in all cells. In a
spreadsheet, such as Excel or the OpenOffice spreadsheet, one can
easily write such an expression in a cell and when this expression is
copied to other cells the references to neighboring cells shift
correctly. If, for instance, you are in cell C4 and want in this cell
to have the maximum of the cells C3, B3 and B4 you should simply write
"=max(C3;B3;B4)" in the cell. When this is copied and pasted to cell E7
(using ctrl-c and ctlr-v) it automatically becomes "=max(E6;D6;D7)" as
it should.
1. Use the above idea to do Needleman-Wunch on two sequences with a gap
penalty of 2, a match score of 1 and a mismatch score of -2. First
create a matrix of pair scores s(xi,xj)
either manually or by a spreadsheet formula. Then calculate the
dynamic programming matrix. Make sure that the scores and penalties can
easily be changed by changing just one number somewhere. You can use
the example sequences in chapter 2 of the book.
2. Here is an Excel file with the BLOSUM 50
substitution matrix and a formula to score sequences with the matrix
(should be possible to open with openoffice). Build on this this to
recreate the DP matrix shown in Figure 2.5 in the book (without the
back-tracking information).
Anders Krogh, Nov 10, 2005.
Idea: Richard Durbin.