課程名稱︰課程名稱︰ 生物序列分析演算法 課程性質︰ 演算法 課程教師︰ 趙坤茂 開課學院： 電資 開課系所︰ 資工 考試日期（年月日）︰ 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