→ andy74139 :已收錄至資訊系精華區!! 05/24 23:41
課程名稱︰ 生物序列分析演算法
課程性質︰ 演算法
課程教師︰ 趙坤茂
開課學院： 電資
開課系所︰ 資工
考試日期（年月日）︰ 2011.05.24
考試時限（分鐘）： 3H
是否需發放獎勵金： yes
試題：
Problem 1
For a given sequence GTATTCGCTATTCG, construct (a) its hash table
for finding word matches of length 3, (b) its suffix tree, (c) its
suffix array and (d) its hash table for a spaced seed model 1*11
Problem 2
Briefly describe how ungapped BLAST works. What is the two-hit method
for gappd BLAST?
Problem 3
In this problem, you are given a number sequence A = <7,4,3,8,1,6,10,9,1,5>
(a) Draw a left-skew decomposittions for every prefix of A.
(b) Briefly explain why the left-skew decompositions for all prefixes can be
done in linear time.
Problem 4
Consider the tag SNP selection problem for the example in the box.
(a) Give a set cover formulation for it.
(b) Give an integer linear programming formulation for it.
(c) What is the minimum subset of SNPs that can form a set of tag SNPs?
p1 p2 p3 p4
s1 0 1 0 0
s2 1 0 1 1
s3 1 1 0 0
s4 1 0 1 0
s5 0 0 0 1
Problem 5
You are given a numbetr sequence A = <X, a1, a2, ..... an, X>, where X is larger
than any element a1, a2,...an. Design a linear time algorithm for finding the
nearest larger element for every element a1,a2, a3....an of the sequence. Use the
sequence A= <100,7,4,3,8,1,6,10,9,1,5,100> to illustrate your algorithm.
Problem 5
Let X be an algorithm for solving the RMSQ (Range Maximum-sum segment Query) problem
in O(n)-prepocessing time and O(1)-query time, where n is the length of the number
sequence. Show that X can be used to solve the RMQ (Range Minima QUery) problem
for a number sequence ofd length b in O(n)-preprocessing time and O(1)-query time.
Use the sequence A = <7,4,3,8,1,6,10,9,1,5> to illustrate your idea
--
沒有不可能的事, 只有不願做的事
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.46