程序代写 Compsci 369 T3

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