Course: Algorithms for Biological Sequence Analysis   Instructor: Kun-Mao Chao

Midterm exam. April 14, 2003

Note: Both the correctness and efficiency of your algorithms will be evaluated.

1.      (15%) Partition each suffix of the following sequence into right-skew segments of strictly decreasing averages. (Decreasingly Right-Skew Decomposition)
     2  8  2  6  7  1  6  8
Briefly explain the implication of a right-skew pointer.

2.      (15%) Give an algorithm that determines, for each aligned pair (i.e., column) of an optimal alignment, the amount by which the optimum score must be lowered before reaching an alignment not containing that pair. In other words, if the optimum alignment score is s and the aligned pair is assigned the robustness-measuring number r, then any alignment scoring strictly greater than s-r aligns those two sequence positions, while some alignment of score s-r does not align them.

3.      (15%) There are situations where the ith entry of the first sequence can be aligned to the jth entry of the second sequence only if L[i] <= j <= U[i], for given lower and upper bounds L and U. In this problem, we consider the case when the region is a parallelogram, i.e., U[i] = L[i] + W, for some value W. Based on the partition lines defined in the following figure, give a linear-space alignment algorithm whose running time is bounded by a constant times the area of the parallelogram. Justify your answer.









4.      (15%) Describe the sum-of-pairs (SP) scoring scheme for multiple sequence alignment. What is a quasi-gap? Why does the progressive alignment approach work more efficient than the exact method does?

5.      (20%) Assume the following simple scoring scheme:
    A match is given a bonus +8;
    A mismatch is penalized by –5;
    A gap is given a constant penalty –20;
Give the recurrences for computing the score of an optimal global alignment.

6.      (20%) Consider the following coin-tossing problem:

0.7
 

0.3
 

Biased coin (B)
 

Fair coin (F)
 

0.3
 

0.7
 

H: 0.8
T: 0.2
 

H: 0.5
T: 0.5
 







Assume that the probability of starting in state F (fair coin) is 0.5 and that the probability of starting in state B (Biased coin) is also 0.5.
(a) Use the Viterbi algorithm to compute the most probable path for the sequence THHHTH. Show the matrix. Give the state path and its probability.
(b) Use the forward algorithm to determine the probability of the sequence THHHTH. Show the matrix and give the probability of the sequence.