Title page for etd-0106109-080018


[Back to Results | New Search]

URN etd-0106109-080018
Author Chung-Han Chiang
Author's Email Address No Public.
Statistics This thesis had been viewed 5583 times. Download 2020 times.
Department Computer Science and Engineering
Year 2008
Semester 1
Degree Master
Type of Document
Language English
Title A Genetic Algorithm for the Longest Common Subsequence of Multiple Sequences
Date of Defense 2008-07-14
Page Count 57
Keyword
  • longest common subsequence
  • multiple sequences
  • genetic algorithm
  • Abstract Various approaches have been proposed for finding the longest
    common subsequence (LCS) of two sequences. The time complexities
    of these algorithms are usually $O(n^2)$ in the worst case, where
    $n$ is the length of input sequences. However, these algorithms
    would become infeasible when the input length, $n$, is very long.
    Recently, the $k$-LCS $(k ≥ 2)$ problem has become more
    attractive. Some algorithms have been proposed for solving the
    problem, but the execution time required for solving the $k$-LCS
    problem is still too long to be practical. In this thesis, we
    propose a genetic algorithm for solving the $k$-LCS problem with
    time complexity $O(Gpk(n + |P_j|))$, which $G$ is the number of
    generations, $p$ is the number of template patterns, $k$ is the
    number of input sequences, $n$ and $|P_j|$ are the length of input
    sequences and the length of template patterns, respectively. As
    our experimental results show, when $k$ is 20 and $n$ is 1000, the
    performance ratio ($|CS|/|LCS|$) of our algorithm is greater than
    0.8, where $|CS|$ denotes the length of the solution we find, and
    $|LCS|$ represents the length of the real (optimal) LCS. Comparing
    the performance ratios with Expansion Algorithm and BNMAS
    Algorithm, our algorithm is much better than them when the number
    of input sequences varies from 2 to 20 and the length of the input
    sequences varies from 100 to 2000.
    Advisory Committee
  • none - chair
  • none - co-chair
  • none - co-chair
  • none - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0106109-080018.pdf
  • indicate in-campus access immediately and off_campus access in a year
    Date of Submission 2009-01-06

    [Back to Results | New Search]


    Browse | Search All Available ETDs

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