To demonstrate the eﬃciency of our MLCS and BMLCS algorithms, we ﬁrst compare the execution time of our algorithms and some previously published algorithms on pseudorandom sequences. Then we compare the eﬃciency 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 inﬂuences of various length ratios of A and T with ﬁxed |T| in diﬀerent 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 ﬁfth 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 diﬀerent contents in diﬀerent 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(r) ^{2} + 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}.