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 journalJournal articlepeer-review

2 Citations (Scopus)

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 languageEnglish
Pages (from-to)2179-2192
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume35
Issue number3
Early online date30 Sept 2021
DOIs
Publication statusPublished - 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)

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