Thanks

Recall the Edit Distance (Sequence Alignment) problem: given two strings over the same alphabet and mismatch and gap penalties, find an alignment of minimal cost. One of the most common uses of the minimum edit distance algorithm is in computational biology. DNA sequences are composed of four amino-acids, denoted by the letters A, C, T, G. Mutation over the course of evolution changes the sequences by deleting, inserting, or substituting amino-acids. The smaller the edit distance between some two sequences, the smaller the evolutionary distance between them. Thus, biological sequences are often aligned to minimize the edit distance between them. (b) Extra credit: 2 points Suppose there are occasional errors in sequencing and some of the letters in the DNA sequence are represented by a'?' as a result. The '?" character can be matched to any letter in the alignment but not to a gap i. Modify the Sequence Alignment algorithm to account for the '?' charac- ter. Give the recurrence relation and the polynomial dynamic programming algorithm ii. Assume the mismatch and gap costs are as in the previous question. Find the minimum edit distance AND the optimal alignment between the following sequences (show the matrix of your calculations) Sequence 1: GAT?TACA Sequence 2: A TT A C? please solve either part