4. Sequence alignment. When a new gene is discovered, a standard approach to understanding its function is to look through a database of known genes and find close matches. The closeness of two genes is measured by the extent to which they are aligned. To formalize this, think of a gene as being a long string over an alphabet -(A,C,G, T). Consider two genes (strings) x-ATGCC and y-TACGCA. An alignment of r and y is a way of matching up these two strings by writing them in columns, for instance: AT-GCC TA-CGCA Here the "indicates a "gap." The characters of each string must appear in order, and each column must contain a character from at least one of the strings. The score of an alignment is specified by a scoring matrix of size (E +1) ( + 1), where the extra row and column are to accommodate gaps. For instance the preceding alignment has the following score: Give an algorithm that takes as input two strings z 1 .. n and y[1 .. m] and a scoring matrix , and returns the highest-scoring alignment. The running time should be O(mn). Hint: Use Dynamic Programming. Approach the problem as in Problem 2: first design a recursive algorithm, identify the subproblems, and then memoize (you don't need to give an iterative algorithm)