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