### Title page for etd-0106109-080018

URN etd-0106109-080018 Chung-Han Chiang No Public. This thesis had been viewed 5583 times. Download 2020 times. Computer Science and Engineering 2008 1 Master English A Genetic Algorithm for the Longest Common Subsequence of Multiple Sequences 2008-07-14 57 longest common subsequence multiple sequences genetic algorithm Various approaches have been proposed for finding the longestcommon subsequence (LCS) of two sequences. The time complexitiesof these algorithms are usually \$O(n^2)\$ in the worst case, where\$n\$ is the length of input sequences. However, these algorithmswould become infeasible when the input length, \$n\$, is very long.Recently, the \$k\$-LCS \$(k ≥ 2)\$ problem has become moreattractive. Some algorithms have been proposed for solving theproblem, but the execution time required for solving the \$k\$-LCSproblem is still too long to be practical. In this thesis, wepropose a genetic algorithm for solving the \$k\$-LCS problem withtime complexity \$O(Gpk(n + |P_j|))\$, which \$G\$ is the number ofgenerations, \$p\$ is the number of template patterns, \$k\$ is thenumber of input sequences, \$n\$ and \$|P_j|\$ are the length of inputsequences and the length of template patterns, respectively. Asour experimental results show, when \$k\$ is 20 and \$n\$ is 1000, theperformance ratio (\$|CS|/|LCS|\$) of our algorithm is greater than0.8, where \$|CS|\$ denotes the length of the solution we find, and\$|LCS|\$ represents the length of the real (optimal) LCS. Comparingthe performance ratios with Expansion Algorithm and BNMASAlgorithm, our algorithm is much better than them when the numberof input sequences varies from 2 to 20 and the length of the inputsequences varies from 100 to 2000. none - chair none - co-chair none - co-chair none - co-chair Chang-Biau Yang - advisor indicate in-campus access immediately and off_campus access in a year 2009-01-06

Browse | Search All Available ETDs

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