课程名称︰课程名称︰ 生物序列分析演算法 课程性质︰ 演算法 课程教师︰ 赵坤茂 开课学院： 电资 开课系所︰ 资工 考试日期（年月日）︰ 2011.04.12 考试时限（分钟）： 3H 是否需发放奖励金： yes （如未明确表示，则不予发放） 试题 : 1. Suppose we are given a very long DNA sequence where the occurrence probabilities of nucleotides A, C, G, T are 0.3, 0.1, 0.2. and 0.4 respectively. Construct a Huffman code for them. You should work out the binary three construction as well as the code assignment. 2. In class, we introduced an O(nlog n)-time algorithm fore finding a longest increasing subsequence of an input sequence of length n. Use <5,2,4,1,6,8,9,3,7> to explain how the algorithm works. 3. We assume the following simple scoring scheme. A match is given a bonus score 8, a mismatch is penalized by assigning score -5, and the gap penalty for each gap symbol is -3. a. Write down the dynamic-programming matrix for computing an optimal global alignment of the sequences ATGGC and AGGTC. Print the global alignment and its score. b. Write down the dynamic-programming matrix for computing an optimal local alignment of the sequences GATGGCT and TAGGTCG. Print the local alignment and its score. c. Assume further that opening up a gap is charged an additional cost -8. Write down the dynamic-programming matrix for computing an optimal global alignment of the sequences ATGGC and AGGTC. Print the global alignment and its score. 4. Consider the problem of computing all delta-point of two sequences of lengths m and n, where m << n , a. Describe a method for computing all delta-point that runs in O(mn log m) time and O(n) working space. b. Describe a method for computing all delta-point that runs in O(mn)time and O(m^10/9 + n) working space. 5. a. What is the SUm-of-pairs score of the following multiple alignment? b Illustrate how a progressive alignment procedure might deliver the above multiple alignment. -- Nothing is Impossible --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.46