Algorithmic Studies of Sequence Manipulation and Related Problems
Date Issued
2007
Date
2007
Author(s)
Lin, Tien-Ching
DOI
en-US
Abstract
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.
Subjects
序列的最佳化問題
序列的範圍搜尋問題
optimization problems on sequences
range query problems on sequences
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-D89922001-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):140ebc0af6f23ff9dfda6abc84401bc9