1. Multiple string alignment. As in class, we consider the operations of substitution (including the zero-cost substitute-a-letter-for-itself "no-op), insertion, and deletion An alignment of three strings a, y, z (of lengths nz, ny, nz, respectively) is an array of the form That is, in the first row a appears in order, possibly with some gaps, in the second row y does, and in the third row z does. We define the cost of such an alignment as follows. The cost of a column 2 31 is the sum-of-pairs cost, e-g., in the preceding example we look at the cost of aligning 2 with y (a substitution, costing either 0 or 1 depending on whether or not) the cost of aligning r2 with - (a deletion, costing 1), and the cost of aligning yi with -(another deletion), for a total cost of csubs + 2eel = 3 for this one column of the alignment. The total cost of the alignment is the sum of the costs of its columns. Given three strings ,y, z, the goal of Multiple String Alignment is to find a minimum-cost alignment. (a) (15 pts) Give an efficient (polynomial-time) algorithm for finding optimal align- ments of three strings. Describe your algorithm in pseudocode and English, and prove an upper bound on its running time; you do not need to prove correctness (but you will only receive full credit if your algorithm is correct!). Hint 1: start with a recursive algorithm, where the recursion has 7 cases depending on what the last column of the alignment looks like .T m: Hint 2: Your recursive algorithm will likely not be very efficient; what technique can you use from class to improve its efficiency? (b) (7 pts) Consider generalizing your approach to part (a) to k strings instead of 3. How many cases would there be to consider in the recursion? What runtime would the algorithm have? You do not need to give the algorithm, but must argue persuasively that your answers are correct, given your answer to part (a)