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 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 δ of size (|σ| + 1) × (|σ| + 1), where the extra row and column are to accommodate gaps. for instance the preceding alignment has the following score: δ(−, t) + δ(a, a) + δ(t, −) + δ(−, c) + δ(g, g) + δ(c, c) + δ(c, a). give a dynamic programming algorithm that takes as input two strings x[1 . . n] and y[1 . . m] and a scoring matrix δ, and returns the highest-scoring alignment. the running time should be o(mn).