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