Linear Space Alignment $[10$ points$]$ c$.($i$)$ Give the recursion tree, where each vertex corresponds to an invocation of

Hirschberg. See Lecture $1$ for an example of a recursion tree. $($ii$)$ Label each

vertex of this tree by the used arguments $(i,j,i^{\text{'}},j^{\text{'}}).$ In addition, $($iii$)$ label

each internal vertex by the value of $i^{*},$prefix$(i^{*})$ and suffix$(i^{*}).$ Make sure to

include the bases cases as leaves of the tree. $[5$ points$]$

$(i,j,i^{\text{'}},j^{\text{'}})|i^{*}|prefix(i^{*})|suffix(i^{*})$

$\{\begin{array}{ccc}\text{:}[(0,& 0,2,4),& ]\end{array}$

Consider two sequences $v=$ TG and $w=$ ATCG of length $m=|v|=2$ and $n=|w|=$

$4,$ respectively. In this exercise, we will compute an optimal global alignment of the

two sequences using the Hirschberg algorithm. We will use a score of $+1$ for a match,

$-1$ for a mismatch, and $-1$ for a insertion$/$deletion $($i$.$e$.$ a gap penalty of $1).$