To demonstrate the efficiency of our MLCS and BMLCS algorithms, we first compare the execution time of our algorithms and some previously published algorithms on pseudorandom sequences. Then we compare the efficiency of two superior algorithms, our MLCS algorithm and the bit-parallel MLCS algorithm [8], on some real DNA sequences. These algorithms are implemented by Visual Studio C++ 2013 software, and tested on a computer with 64-bit Windows 7 OS, CPU clock rate of 3.2 GHZ (Intel i5-4570) and 32 GB of RAM, or a computer with less power.
We illustrate the influences of various length ratios of A and T with fixed |T| in different similarities. We use the format (|T|, Ratio, |Σ|, Algorithm) to represent the experiments of each chart. When the BMLCS algorithms are compared, the number of blocks is added as the fifth parameter. For example, (2000, *, 64, ?) is used to express charts in left part of Figure 1, where |T| = r = 2000, alphabet size |Σ| = 64, ”*” is a wildcard for representing all possible contents of that parameter, and ”?” means different contents in different charts.
| Name | year | Author(s) | Time complexity | Keywords |
|---|---|---|---|---|
| Merged longest common subsequence algorithms | ||||
| Ours | 2017 | De et al. | O(n|Σ| + (r − L + 1)Lm) | Diagonal Extension and Domination |
| Rahman | 2014 | Rahman and Rahman | O((Rn + Pm) loglog n) | Bounded heap |
| Deorowicz | 2013 | Deorowicz and Danek | O(⌈r / w⌉mn logw) | Bit-Parallel |
| Peng | 2010 | Peng et al. | O(Lrm) | Sparse Dynamic Programming |
| Huang | 2008 | Huang et al. | O(rnm) | Dynamic programming | Block merged longest common subsequence algorithms |
| Ours | 2017 | De et al. | O(n|Σ| + (r − L + 1)Lδ) | Diagonal Extension and Domination |
| Rahman | 2014 | Rahman and Rahman | O(max{Rβloglog n, Pαloglog n}) | Bounded heap |
| Deorowicz | 2013 | Deorowicz and Danek | O((mβ + nα)⌈r / w⌉ + αβ⌈r / w⌉) | Bit-Parallel |
| Peng | 2010 | Peng et al. | O(Lrδ) | Sparse Dynamic Programming |
| Huang | 2008 | Huang et al. | O(rnδ) | Dynamic programming |
| Huang | 2008 | Huang et al. | O(r2 + rδ2 ) | S-table |
Each figure shows the execution time of an algrithm with length of string T(r) =2000, alphabet size = 64 and algorithm = {DP, Peng, Rahman, Bit, Ours}.
Each figure shows the execution time of an algrithm with length of string T(r) =5000, alphabet size = 1000 and algorithm = {DP, Peng, Rahman, Bit, Ours}.
Each figure shows the execution time of an algrithm with length of string T(r) =2000, ratio = 0.5 and alphabet size = {4, 64, 1000}.
Each figure shows the execution time of an algrithm with length of string T(r) =5000, ratio = 0.5 and alphabet size = {4, 64, 1000}.
Each figure shows the execution time of an algrithm with block = 5, length of string T(r) =2000, ratio = 0.5 and alphabet size = {4, 64, 1000}.
Each figure shows the execution time of an algrithm with block = 5, length of string T(r) =5000, ratio = 0.5 and alphabet size = {4, 64, 1000}.
Each figure shows the execution time of an algrithm with block = 10, length of string T(r) =2000, ratio = 0.5 and alphabet size = {4, 64, 1000}.
Each figure shows the execution time of an algrithm with block = 10, length of string T(r) =5000, ratio = 0.5 and alphabet size = {4, 64, 1000}.
