There are two sequences TGAGA and CATAGCC. A linear gap penalty of $-2($per gap$),$ a

score of $+2\mathrm{.}5$ for matches and $-1$ for mismatches are given. Please note that here a score for

matches is $2\mathrm{.}5.$

A $(25$ marks$).$ Use the Needleman$-$Wunsch algorithm to find an optimal$-$scoring alignment of

the two sequences. Your answer must include a completely populated grid of sub$-$alignment

scores.

B $(5$ marks$).$ How many equally optimal alignments are there for the pair of sequences in the

previous question?

C $(25$ marks$).$ Use the Smith$-$Waterman algorithm to find an optimal$-$scoring local alignment

of these two sequences. Your answer must include a completely populated grid of sub$-$

alignment scores.

D $(25$ marks$).$ Use the shortest path approach, to find an optimal$-$scoring alignment of the two

sequences. Your answer must include details: show the graph, mark the edges with weights,

show the sub$-$alignment scores, and mark the shortest path. The weights are defined as below:

d$($a$,-)=$d$(-,$a$)=+2$; d$($a$,$b$)=+1$ if a $$ b; d$($a$,$b$)=-2\mathrm{.}5$ if a$=$b$.$

E $(20$ marks$).$ Consider another setting: a linear gap penalty of $-1($per gap$),$ a score of $+2$ for

matches and $-3$ for mismatches. Use the Needleman$-$Wunsch algorithm to find an optimal$-$

scoring alignment of the two sequences: GTATA and GATC. Your answer must include a

completely populated grid of sub$-$alignment scores, and show all equally optimal alignments.

$[$Note this is example that in the optimal assignment, it is possible that a vertical move is

followed by a horizontal move, as explained during the lecture.$]$