Heuristic Algorithms for Finding the Longest Common Subsequence of Multiple Sequences

Finding the Longest Common Subsequence of multiple sequences is an interesting and important problem in many areas, such as computer science and bioinformatics. Since its importance, some algorithms with about time complexity O(n^2) have been proposed for finding the LCS of two sequences, where n is the length of sequences. For k sequences(k > 2), this problem will be become to a NP-hard problem. Finding the exact LCS of large number and length of sequences takes very long time and thus will become impractical, many heuristic algorithms have been proposed. In this thesis, two heuristic algorithms is presented for finding the Longest Common Subsequence of Multiple Sequences. The time complexities of our algorithms are O(|Σ|^2n(k + |Σ|)), where Σ is the set of symbols, k and n are the number and the length of input sequences, respectively. In the experi- mental results, our algorithms finds the common subsequences whose lengths are about 7.33% more than the Best Next for Maximal Available algorithm in average for random sequences with uniform distribution [1]. In the different symbol sizes experimentat, the result shows that our methods are also suitable for complicated sequences.