课程名称︰ 生物序列分析演算法 课程性质︰ 演算法 课程教师︰ 赵坤茂 开课学院： 电资 开课系所︰ 资工 考试日期（年月日）︰ 2010.04.18 考试时限（分钟）： 3H 是否需发放奖励金： yes 试题： Problem 1: In this problem, you are given a number sequence A = <8,3,5,7,9,6,8,5,9,6> a. Draw a left-skew decomposition for every prefix of A. b. Use this example sequence to explain why the left-skew decomposition can be used to find the maximum-average segment dending at each index of A. c. Use this example sequence to explain why the left -skew decomposition for all prefixes can be done in linear time. d. Draw a right skew decomposition for every suffix of A. Problem 2. Given a number sequence A = <a1,a2,.....an> design a linear time algorithm for finding the nearest smaller element for every element of the sequence Problem 3 Given an algorithm that solves the RMQ(Range Minima Query) problem in O(n log n) prepocessing time and O(1) query time, where n is the length of the number sequence. (Hint: For each index,compute the minima of the segments starting from it which are of lengths 1,2,4,8,...) Problem 4 Let X be an algorithm for solving the RMSQ(Range Maximum-Sum Segment Query) problem in O(g(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 of length n in O(g(n)+n)-prepocessing time and O(1) query time. Problem 5 The goal of the International HapMap Project is to develop a haplotype map of the human genemo, the HapMap, which will describe the common patterns of human DNA sequence variation. a. Define the haplotype inference problem b. Five an Integer Quadratic Programming formulation for haplotype inference. c. What are tag SNPs? d. Use an example to show how to reduce the tag SNP problem to the minimum test set problem introduced in class. e. Use an example to describe the idea of LD bins. -- 叶子的离开, 是因为风的追求, 还是树的不挽留 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.46