课程名称︰ 生物序列分析演算法 课程性质︰ 演算法 课程教师︰ 赵坤茂 开课学院： 电资 开课系所︰ 资工 考试日期（年月日）︰ 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