Title page for etd-0020114-165412


[Back to Results | New Search]

URN etd-0020114-165412
Author Yi-pu Guo
Author's Email Address No Public.
Statistics This thesis had been viewed 5352 times. Download 543 times.
Department Computer Science and Engineering
Year 2013
Semester 1
Degree Master
Type of Document
Language English
Title Efficient Algorithms for the Flexible Longest Common Subsequence Problem
Date of Defense 2014-01-08
Page Count 57
Keyword
  • Dominant Strategy
  • Flexible Longest Common Subsequence
  • Longest Common Subsequence
  • Dynamic Programming
  • Sequence Alignment
  • Abstract Given two sequences, the traditional longest common subsequence (LCS) problem is to obtain the common subsequence with the maximum number of matches, without considering the continuity of the matched characters. However, in many applications, the alignment results with higher continuity are more meaningful than the sparse ones, even if the number of matched characters is a little lower. Accordingly, we define a new variant of the LCS problem, called the flexible longest common subsequence (FLCS) problem. In this thesis, we design a scoring function to estimate the continuity of an alignment between two strings, and develop efficient algorithms for solving the FLCS problem. We first propose a straightforward method with the dynamic programming approach, which requires O(n^3) time, where n denotes the longer length of the input sequences. Then, we apply the concept of dominant lists to reduce the redundant computation in each lattice cell. Finally, we propose an efficient algorithm for solving the FLCS problem with O(mn) time, where m and n denote the lengths of the two input sequences.
    Advisory Committee
  • Jen-Chih Yao - chair
  • Chia-Ping Chen - co-chair
  • Kuo-Si Huang - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0020114-165412.pdf
  • Indicate in-campus at 0 year and off-campus access at 1 year.
    Date of Submission 2014-01-20

    [Back to Results | New Search]


    Browse | Search All Available ETDs

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