Question 1

1OUTPUTLCS(Backtrack, v, i, j)
2  if i = 0 or j = 0
3    return
4  if Backtrack_{i,j} = ↓
5    OUTPUTLCS([    I    ])
6  else if Backtrack_{i,j} = →
7    OUTPUTLCS([    II    ])
8  else
9    OUTPUTLCS([    III    ])
10    output v_i

Given below is the algorithm to print the longest common subsequence between the $i$-prefix of $v$ and the $j$-prefix of $w$. The matrix $\mathit{Backtrack}$ stores the directions along which the algorithm should perform the backtracking operation in the form of arrows. Fill the given blanks to complete the algorithm. OUTPUTLCS(Backtrack, v, i, j) if i = 0 or j = 0 return if Backtrack_{i,j} = ↓ OUTPUTLCS([ I ]) else if Backtrack_{i,j} = → OUTPUTLCS([ II ]) else OUTPUTLCS([ III ]) output v_i Calculate the optimal global alignment score for the DNA sequences GAATTC and GATTA. Scoring is done as follows:\ • For every match: +2 points\ • For every mismatch: -1 points\ • For every insertion or deletion: -2 points Figure from the original question paper