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 sigma = {A, C, G, T}. Consider two genes (strings) x = ATGCC and y = TACGCA. An alignment of x and y is a way of matching up these two strings by writing them in columns, for instance: - A T - G C C T A - C G C A 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 delta of size (|sigma| + 1) times (|sigma| + 1), where the extra row and column are to accommodate gaps. For instance, the preceding alignment has the following score: delta (-, T) + delta (A, A) + delta (T, -) + delta (-, C) + delta (G, G) + delta (C, C) + delta (C, A). Give a dynamic programming algorithm that takes as input two strings x [1 ... n] and y [1 ... m] and a scoring matrix delta, and returns the highest-scoring alignment. The running time should be O (mn).