Title page for etd-0720113-163337


[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
  • etd-0720113-163337.pdf
  • Indicate in-campus at 0 year and off-campus access at 1 year.
    Date of Submission 2013-08-20

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys