Question $1$: You are given strings $x=$ GTATA and $Y=$ GAGT as an input for the Sequence Align$-$

ment problem. You are asked to populate step$-$by$-$step the array of the dynamic programming

algorithm for the given $x,Y$ instance $($like the step$-$by$-$step solutions we saw in class for the Knap$-$

sack$).$ For each step, show the current content of the array $A,$ as well as the values of $i,j,$ and

the three values considered in the minimization problem. Apply the above for the following two

scenarios:

$($i$)$ The penalty of a gap mismatch is ${}_{\text{g}\text{a}\text{p}}=4,$ and the penalty of a letter mismatch is ${}_{xY}=3.$

$($ii$)$ This time, the penalty of a gap mismatch is ${}_{\text{g}\text{a}\text{p}}=5,$ and the penalty of a letter mismatch is

${}_{xY}=3.$

Notice that, if the two letters do match, e$.$g$.,{}_{AA},{}_{GG},{}_{TT},{}_{CC},$ then the penalty is $0.$ Is

the optimal alignment the same for the two parameterizations? If not, give an intuitive$/$informal

explanation of why they differ.