Sequence alignment. When a new gene is discovered, a standard approach to under standing 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 a gene as being a long string over the alphabetz {A,C,G,T). Consider two genes (strings) rATGCC and y TACGCA. An alignment of a and y is a way of matching up these two strings by writing them in columns, for instance: A T G C C C GC A Here the indicates a "gap". The characters of each string must appear in order, and each column must contain a character at least one of the strings. The score of an alignment is specified by a scoring matrix of size (|| + 1) ( + 1), where the extra row and column are to accommodate gaps. For example the preceding alignment has the following score: Give a dynamic prograinming algorithm that takes as input two strings x[1n] and y[L..Tn] and a scoring matrix , and returns the highest-scoring alignment. The running time should be O(mn)