A Branch Elimination-based Efficient Algorithm for Large-scale Multiple Longest Common Subsequence Problem

Shiwei Wei, Yuping Wang*, Yiu Ming Cheung

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 node. 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 languageEnglish
JournalIEEE Transactions on Knowledge and Data Engineering
DOIs
Publication statusE-pub ahead of print - 30 Sep 2021

User-Defined Keywords

  • multiple longest common subsequences(MLCS)
  • dominant point-based approach
  • useless match point detection
  • branch elimination
  • smaller DAG

Fingerprint

Dive into the research topics of 'A Branch Elimination-based Efficient Algorithm for Large-scale Multiple Longest Common Subsequence Problem'. Together they form a unique fingerprint.

Cite this