Title page for etd-0819109-141733


[Back to Results | New Search]

URN etd-0819109-141733
Author Hsiang-yi Weng
Author's Email Address No Public.
Statistics This thesis had been viewed 5559 times. Download 1561 times.
Department Computer Science and Engineering
Year 2008
Semester 2
Degree Master
Type of Document
Language English
Title A Hybrid Algorithm for the Longest Common Subsequence of Multiple Sequences
Date of Defense 2009-07-07
Page Count 67
Keyword
  • Ant Colony Optimization Algorithm
  • genetic algorithm
  • longest common subsequence
  • Abstract The k-LCS problem is to find the longest common subsequence (LCS) of k input sequences. It is difficult while the number of input sequences is large.
    In the past, researchers focused on finding the LCS of two sequences (2-LCS). However, there is no good algorithm for finding the optimal solution of k-LCS up to now. For solving the k-LCS problem, in this thesis, we first propose a mixed algorithm, which is a combination of a heuristic algorithm, genetic algorithm (GA) and ant colony optimization (ACO) algorithm.
    Then, we propose an enhanced ACO (EACO) algorithm, composed of the heuristic algorithm and matching pair algorithm (MPA). In our experiments, we compare our algorithms with expansion algorithm, best next for maximal available symbol algorithm, GA and ACO algorithm. The experimental results on several sets of DNA and protein sequences show that our EACO algorithm outperforms other algorithms in the lengths of solutions.
    Advisory Committee
  • Shen-Chuan Tai - chair
  • Chung-nan Lee - co-chair
  • Shyue-Horng Shiau - co-chair
  • Kuo-Si Huang - co-chair
  • Chang-Biau Yang - advisor
  • Files
  • etd-0819109-141733.pdf
  • indicate in-campus access immediately and off_campus access in a year
    Date of Submission 2009-08-19

    [Back to Results | New Search]


    Browse | Search All Available ETDs

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