[Back to Results | New Search]

URN etd-0720113-163337 Author Chiou-Ting Tseng Author's Email Address No Public. Statistics This thesis had been viewed 5350 times. Download 302 times. Department Computer Science and Engineering Year 2012 Semester 2 Degree Ph.D. Type of Document Language English Title Variants of the Constrained Longest Common and Longest Increasing Subsequence Problems Date of Defense 2013-05-17 Page Count 115 Keyword design of algorithms bioinformatics longest common subsequence finite automata sequential substring height longest increasing subsequence NP-hard constrained LCS Abstract Given two strings A = a1a2a3...am and B = b1b2b3...bn, the longest

common subsequence (LCS) problem is that of finding the longest common

part of A and B by deleting zero or more characters from A and B. Given

a string S = a1a2a3...am, composed of comparable elements, the longest

increasing subsequence (LIS) problem is that of finding a subsequence of

S such that the subsequence is increasing and its length is maximal. The

constrained LCS (CLCS) or constrained LIS (CLIS) problem is that of finding

the longest subsequence satisfying the given constraint C. In this dissertation,

we propose and solve several variants of the LCS and LIS problems, which

are (1) the sequential substring CLCS problem, (2) the string-exclusion

CLCS problem, (3) the minimum height LIS problem and (4) the sequence

constrained LIS problem.

Given an ordered set of constraint substrings (C^1, C^2,... , C^h) with

total length r, the sequential substring CLCS problem is that of finding the

CLCS of A and B containing all constraint substrings as substrings and the

order of them are retained. This problem has two variants, depending on

whether the strings cannot overlap or may overlap. We propose algorithms

with O(mnh + (m + n)(|Σ| + r)) and O(mnr + (m + n)|Σ|) time for the two

variants, respectively. When there is a single constraint substring, i.e., the

string-inclusion CLCS problem, our algorithm runs in O(mn+(m+n)(|Σ|+r))

time which improves the previous O(mnr)-time algorithm.

The string-exclusion CLCS is that of finding the LCS excluding C as a

substring. We propose an O(mnr)-time algorithm for it even if there are

multiple constraints with total length r.

The minimum height LIS problem is that of finding the ones with minimum

difference between the first element and the last element among the LIS's.

We propose an algorithm with O(n log n)-time and O(n)-space to solve it.

The sequence constrained LIS problem is that of finding the CLIS of A

containing C. We propose two variants of this problem, without or with

preprocessing. We solve the first one with time complexity O(n log(n + |C|)).

For the second one, after an O(n^2 log log n)-time preprocessing, we can answer one query in O(|C| + |OUTPUT|) time where OUTPUT is the answer to the query.Advisory Committee Mao-Hsiang Chang - chair

Bang-Ye Wu - co-chair

Yaw-Ling Lin - co-chair

Tzung-Pei Hong - co-chair

Yue-Li Wang - co-chair

Biing-Feng Wang - co-chair

Sun-Yuan Hsieh - co-chair

Kun-mao Chao - co-chair

Chang-Biau Yang - advisor

Files Indicate in-campus at 0 year and off-campus access at 1 year.

etd-0720113-163337.pdf Date of Submission 2013-08-20