2.Solve the DNA sequencing problem worksheet (attached). A diagonal move is worth 1, horizontal and vertical moves are worth 0.

a. Show the correspondence between the two strings found by the optimal solution. What is the matching value of this solution?

b. Define the recursive relations and base cases used to calculate the optimal path, e.g. cij = ?

It is not obvious how to align the sequences to get the most correspondences between them. The diagonal arrows show possible correspondences The horizontal and vertical arrows allow you to skip over letters that don't correspond. The goal is to start in the upper left corner and find the path to the lower right that uses as many diagonal arrows as possible; the diagonal paths you take are the correspondences you make It is clear how to align the first letter of the sequences, A with T. No correspondence. Keep track of this by putting 0 in the upper left circle. The best way to align AG with TCG is to align the G's. That gives one correspondence, so put a 1 in the circle 3 down and 4 over to keep track. Continue to fill in each circle using the larger of the number above and the number to the left and, if a diagonal arrow points into the circle you are looking at, one plus the number up and to the left. What number do you get in the lower right corner? What path got you there? It is not obvious how to align the sequences to get the most correspondences between them. The diagonal arrows show possible correspondences The horizontal and vertical arrows allow you to skip over letters that don't correspond. The goal is to start in the upper left corner and find the path to the lower right that uses as many diagonal arrows as possible; the diagonal paths you take are the correspondences you make It is clear how to align the first letter of the sequences, A with T. No correspondence. Keep track of this by putting 0 in the upper left circle. The best way to align AG with TCG is to align the G's. That gives one correspondence, so put a 1 in the circle 3 down and 4 over to keep track. Continue to fill in each circle using the larger of the number above and the number to the left and, if a diagonal arrow points into the circle you are looking at, one plus the number up and to the left. What number do you get in the lower right corner? What path got you there