Abstract
It is a key issue to find out all longest common subsequences of multiple sequences over a set of finite alphabets, namely MLCS problem, in computational biology, pattern recognition and information retrieval, to name a few. However, it is very challenging to tackle the large-scale MLCS problem effectively and efficiently due to the high complexity of time and space. To this end, this paper will therefore propose a Branch Elimination-based Space and Time efficient algorithm called BEST-MLCS, which includes the following four key strategies: 1) Estimation scheme for the lower bound of the length of MLCS. 2) Estimation scheme for the upper bound of the length of the paths through the current match point. 3) Branch elimination strategy by finding all useless match points and removing the branches not on the longest paths. 4) A new Directed Acyclic Graph (DAG) construction method for constructing the smallest DAG among the existing ones. As a result, the proposed algorithm BEST-MLCS can save a lot of space and time and can handle much larger scale MLCS problems than the existing algorithms. Extensive experiments conducted on biological DNA sequences show that the performance of the proposed algorithm BEST-MLCS outperforms three state-of-the-art algorithms in terms of run-time and memory consumption.
Original language | English |
---|---|
Pages (from-to) | 2179-2192 |
Number of pages | 14 |
Journal | IEEE Transactions on Knowledge and Data Engineering |
Volume | 35 |
Issue number | 3 |
Early online date | 30 Sept 2021 |
DOIs | |
Publication status | Published - 1 Mar 2023 |
Scopus Subject Areas
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics
User-Defined Keywords
- branch elimination
- dominant point-based approach
- multiple longest common subsequences(MLCS)
- smaller DAG
- useless match point detection
- Multiple longest common subsequences(MLCS)