Compsci 369 T3
Copyright By PowCoder代写 加微信 powcoder
Compsci 369 – Tutorial 3
1) Linear and affine gap penalties
Alignment 1:
Alignment 2:
Question 1a: Linear penalty: calculate the scores of the above DNA alignments if the score of a match is 2, a mismatch is -1 and a gap is -3.
Alignment 1:
Alignment 2:
Question 1b: Affine penalty: calculate the scores of the above DNA alignments if the score of a match is 2, a mismatch is -1, the gap opening penalty is -5 and the gap extension penalty is -1.
Alignment 1:
Alignment 2:
2) Optimal alignment recurrence relations
Let $S(a,b)$ be the score matrix of matching/mismatching, and let $d$ be the gap penalty. Let $x$ and $y$ be two sequences of length $m$ and $n$ respectively. Then, $F(i,j)$ is the recurrence relation for building the optimal sequence alignment between sequences $x$ and $y$. For each algorithm below, give i) the recurrence relation $F$, ii) the base cases, iii) where to start the traceback to find the optimal alignment, and iv) where to finish the traceback. The Needleman-Wunsch algorithm has been done for you.
Algorithm 1: Needleman-Wunsch algorithm
Recurrence relation:
$$ F(i,j) = \max \begin{cases}
F(i-1,j-1) + S(x_i,y_j) \\
F(i,j-1) + d \\
F(i-1,j) + d
\end{cases} $$
Base cases:
$$F(0,0) = 0, \;\;\; F(i,0) = id \text{ for } i>0, \;\;\; F(0,j) = jd \text{ for } j>0 $$
Start traceback at:
the bottom right cell $F(m,n)$
End traceback at:
the top left cell $F(0,0)$
Algorithm 2: Smith-Waterman algorithm
Recurrence relation:
Base cases:
Start traceback at:
End traceback at:
Algorithm 3: Overlap alignment
Recurrence relation:
Base cases:
Start traceback at:
End traceback at:
3) Smith &
Question 3: Using the Smith/Waterman algorithm, with a match score of +2, a mismatch score of -1 and a gap score of -3, fill out the table below and find the optimal alignment(s) of sequences 1 and 2.
– G T A T G
What is the score of an optimal alignment?
Optimal local alignment(s):
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com