CPSC536a - Assignment 2 (covers Module 2)

handed out Thurs, 01/02/01; due Thurs, 01/02/08

1 Local Alignment [10 marks]

Here is table resulting from a run of the local alignment algorithm (with linear gap penalty with d = -8) on the protein sequences ALSALS ans ANAALL, using the Blosum50 matrix:

A L S A L S
0 0 0 0 0 0 0
A 0 5 0 1 5 0 1
N 0 0 1 1 0 1 1
A 0 5 0 2 6 0 2
A 0 5 3 1 ? 4 1
L 0 0 ? 2 0 12 4
L 0 0 5 7 ? 5 9

(a) Complete the table, by replacing the "?"'s with the appropriate numbers.

(b) From the table, give the optimal local alignment for these two sequences.

2 Alignment in Linear Space [8 marks]

Exercise 2.11, page 36, Chapter 2 of "Biological sequence analysis by Durbin et al.

As a bonus (for 5 marks), particularly if you already have algorithms background, you might also want to try exercise 2.12.

3 Multiple Sequence Alignment [10 marks]

(a) Determine the sum-of-pairs scores for the following multiple sequence alignment, using the Blosum 50 matrix and linear gap penalties with d = -8.

PAWH
PT-I
PA--

(b) Align the following two profiles of DNA sequences. Use the score matrix in which a match gets a value of +2, a mismatch gets a value of -1, and a (base,gap) pair gets a value of -4. (A (gap,gap) pair gets a value of 0.)

Profile 1:
ACGC
AG-C

Profile 2:
ACCT
ACC-