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: 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$dotsn$]$ and $y[1$dotsm$]$ and a scoring matrix $,$ and returns the highest scoring alignment. Give the definition, Base case, solution and formula