Effi cient Merged Longest Common Subsequence Algorithms for Similar Sequences
| Autor: | De-Sheng Chan, 詹德勝 |
|---|---|
| Rok vydání: | 2015 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 104 Given a pair of merging sequences A and B and a target sequence T, the merged longest common subsequence (MLCS) problem is to find out a longest common subsequence (LCS) between sequences E(A, B) and T, where E(A, B) is obtained from merging two subsequences of A and B. In this thesis, we first propose an algorithm for solving the MLCS problem in O(L(r-L+1)m) time, where r and L denote the lengths of T and MLCS length, respectively, and m denotes the minimum length of A and B. From the time complexity, it is clear that our algorithm is extremely efficient when T and E(A, B) are very similar. On the other hand, it is also efficient when the similarity is extremely low. With slight modification, our algorithm can also solve another variant merged LCS problem, the block-merged LCS problem, in O(L(r-L+1)m) time. Experimental results show that our algorithms are faster than other previously published MLCS and BMLCS algorithms for sequences with high similarity. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|