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}.Considertwogenes(strings) x = AT GCC and y = T ACGCA. 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).