Return to search

A Hybrid Algorithm for the Longest Common Subsequence of Multiple Sequences

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.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0819109-141733
Date19 August 2009
CreatorsWeng, Hsiang-yi
ContributorsKuo-Si Huang, Shen-Chuan Tai, Chang-Biau Yang, Chung-nan Lee, Shyue-Horng Shiau
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0819109-141733
Rightsoff_campus_withheld, Copyright information available at source archive

Page generated in 0.0017 seconds