Dynamic Programming Example:

The answer is given. Please give me a better explanation and how to fill in the matrice completely! Much appreciated.

no time involvea; simulated annealing is just a better sampling technique. 11) We want to find the best alignment(s) between the DNA sequences AGTATCT and AGATGC. The scoring scheme S is defined as follows: S(i,j)-1 ifi-j, and S(ij)- 0 otherwise There is a constant gap penalty of -1 (penalty for the first position counts; see table below). The score Sbest and the number N of optimal alignments are (show your final dynamic programming matrix and the best possible alignment (s) for full credit) 0 A) Sbest- 3, N-2 B) Sbest-3, N-1 C) Sbest-4,N-1 E) Sbest-4; N-3