→ andy74139 :已收錄至資訊系精華區!! 05/15 20:26
課程名稱︰課程名稱︰ 生物序列分析演算法
課程性質︰ 演算法
課程教師︰ 趙坤茂
開課學院： 電資
開課系所︰ 資工
考試日期（年月日）︰ 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