 ### Title page for etd-0720113-163337

URN etd-0720113-163337 Chiou-Ting Tseng No Public. This thesis had been viewed 5350 times. Download 302 times. Computer Science and Engineering 2012 2 Ph.D. English Variants of the Constrained Longest Common and Longest Increasing Subsequence Problems 2013-05-17 115 design of algorithms bioinformatics longest common subsequence finite automata sequential substring height longest increasing subsequence NP-hard constrained LCS Given two strings A = a1a2a3...am and B = b1b2b3...bn, the longestcommon subsequence (LCS) problem is that of finding the longest commonpart of A and B by deleting zero or more characters from A and B. Givena string S = a1a2a3...am, composed of comparable elements, the longestincreasing subsequence (LIS) problem is that of finding a subsequence ofS such that the subsequence is increasing and its length is maximal. Theconstrained LCS (CLCS) or constrained LIS (CLIS) problem is that of findingthe longest subsequence satisfying the given constraint C. In this dissertation,we propose and solve several variants of the LCS and LIS problems, whichare (1) the sequential substring CLCS problem, (2) the string-exclusionCLCS problem, (3) the minimum height LIS problem and (4) the sequenceconstrained LIS problem.Given an ordered set of constraint substrings (C^1, C^2,... , C^h) withtotal length r, the sequential substring CLCS problem is that of finding theCLCS of A and B containing all constraint substrings as substrings and theorder of them are retained. This problem has two variants, depending onwhether the strings cannot overlap or may overlap. We propose algorithmswith O(mnh + (m + n)(|Σ| + r)) and O(mnr + (m + n)|Σ|) time for the twovariants, respectively. When there is a single constraint substring, i.e., thestring-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 asubstring. We propose an O(mnr)-time algorithm for it even if there aremultiple constraints with total length r.The minimum height LIS problem is that of finding the ones with minimumdifference 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 Acontaining C. We propose two variants of this problem, without or withpreprocessing. 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. 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 Indicate in-campus at 0 year and off-campus access at 1 year. 2013-08-20

Browse | Search All Available ETDs