李德財臺灣大學：資訊工程學研究所林添進Lin, Tien-ChingTien-ChingLin2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/53996本論文主要在研究兩類問題：序列的最佳化問題(optimization problems on sequences)與序列的範圍搜尋問題(range query problems on sequences)。我們會將與這兩類問題相關的所有問題做全面地概述並依據問題難易程度做分類，介紹解決這兩類問題的技巧，並討論它們的一些應用。 我們會先研究：序列的最佳化問題。我們會把研究焦點放在序列和的選擇問題(Sum Selection Problem)，這個問題是三個很有名的問題的推廣，包括：計算生物學上的最大序列和問題(Maximum Sum Problem)、有限長度的最大序列和問題(Maximum-Sum Segment Problem)與在資訊科學上的選擇問題(Selection Problem)。我們會對序列和的選擇問題分別給出一個隨機的演算法與一個決定性的演算法。我們接著會將這二個演算法結合序列和的範圍搜尋問題(Sum Range Query Problem)的演算法來給出二個前k大序列和問題(k Maximum Sums Problem)的演算法，這二個演算法均改進了目前這個問題的最佳演算法。 我們然後研究序列密度的選擇問題(Density Selection Problem)，這個問題也是三個很有名的問題的推廣，包括：計算生物學上的有限長度的最大序列密度問題(Maximum-Density Segment Problem)、計算幾何學上的斜率選擇問題(Slope Selection Problem)與在資訊科學上的選擇問題(Selection Problem)。我們會對序列密度的選擇問題給出一個最佳的隨機演算法。我們接著會將這個演算法結合序列密度的範圍搜尋問題(Density Range Query Problem)的演算法來給出一個前k大序列密度問題(k Maximum Densities Problem)最佳的隨機演演算法。 我們也研究了有限長度的最大序列密度問題的另一個推廣問題稱之為序列密度的找尋問題(Density Finding Problem)。對於沒有寬度上界的情況，我們會給出一個最佳的演算法。但對於一般的情況，我們只給出一個次佳的演算法。另外，我們也給出有限長度的最大序列密度問題的另一個最佳的演算法。 接著我們會研究：序列的範圍搜尋問題，包括：序列和的範圍搜尋問題(Sum Range Query Problem) 序列密度的範圍搜尋問題(Density Range Query Problem)。對於這二個問題，我們分別給出一個報導模式(reporting mode)與計數模式(counting mode)的演算法。對於序列密度的範圍搜尋問題我們證明了這二個演算法都是最佳的。這二個問題對於在解決序列的最佳化問題上有很大的應用。The dissertation will focuses on the optimization problems on sequences and range query problems on sequences. We will survey and classify the related problems, introduce some techniques for solving these kinds of problems and, discuss their possible biological applications. We first consider some optimization problems on sequences. We focus on the Sum Selection Problem which is a generalization of several famous problems, including Maximum Sum Problem, Maximum-Sum Segment Problem in computational biology, and Selection Problem in computer science. We will give a randomized algorithm and a deterministic algorithm for this problem respectively, and combine them with the algorithm for the Sum Range Query Problem to give two improved algorithms for the k Maximum Sums Problem. We then consider the Density Selection Problem, which is also a generalization of several famous problems, including Maximum-Density Segment Problem in computational biology, Slope Selection Problem computational geometry, and Selection Problem in computer science. We will give an optimal randomized algorithm for this problem and combine it with the algorithm for the Density Range Query Problem to give an optimal algorithm for the k Maximum Densities Problem. We also consider another generalization of Maximum-Density Segment Problem called Density Finding Problem. We give an optimal algorithm for the Density Finding Problem for the case when there is no upper bound on the width of the sequence, and an algorithm for general case. As a byproduct, we give another optimal time algorithm for the Maximum-Density Segment Problem.1 Introduction 1 1.1 Biological Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Theoretical Foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Relationship to Traditional Computational Problems . . . . . . . . . . . . . 3 1.4 Basic Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5.1 Related optimization problems on sequences . . . . . . . . . . . . . . 5 1.5.2 Related range query problems on sequences . . . . . . . . . . . . . . 10 1.6 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Optimization Problems on sequences: Sum Selection Problem 13 2.1 Reduction to a Geometric Intersection Selection Problem . . . . . . . . . . . 13 2.2 Deterministic Algorithm for Sum Selection Problem and k Maximum Sums Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Randomized Algorithm for Sum Selection Problem and k Maximum Sums Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3 Optimization Problems on sequences: Density Selection Problem 40 3.1 Reduction to a Geometric Slope Selection Problem . . . . . . . . . . . . . . 40 3.2 Randomized Algorithm for Density Selection Problem and k Maximum Densities Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4 Optimization Problems on sequences: Density Finding Problem 49 4.1 Reduction to a Geometric Slope Finding Problem . . . . . . . . . . . . . . . 49 iv 4.2 Algorithm for Density Finding Problem . . . . . . . . . . . . . . . . . . . . . 53 4.2.1 Special case when u = w(1; n) . . . . . . . . . . . . . . . . . . . . . . 54 4.2.2 General case when u < w(1; n) . . . . . . . . . . . . . . . . . . . . . . 59 4.3 Algorithm for Maximum-Density Segment Problem . . . . . . . . . . . . . . 62 5 Range Query Problems on sequences 69 5.1 Sum Range Query Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2 Density Range Query Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6 Conclusion 77 6.1 Techniques for Sequence Analysis . . . . . . . . . . . . . . . . . . . . . . . . 77 6.2 Future Research Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78598937 bytesapplication/pdfen-US序列的最佳化問題序列的範圍搜尋問題optimization problems on sequencesrange query problems on sequencesthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53996/1/ntu-96-D89922001-1.pdf