A Branch Elimination-Based Efficient Algorithm for Large-Scale Multiple Longest Common Subsequence Problem

Shiwei Wei

doi:10.1109/TKDE.2021.3115057

2021-01-01

Shiwei Wei

Yuping Wang *

Yiu‐ming Cheung

DOI：10.1109/TKDE.2021.3115057

原文链接

原文求助

摘要

En 中文

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.

Keyword:

Sorting

Memory management

Estimation

Computer science

Upper bound

Merging

Heuristic algorithms

Multiple longest common subsequences(MLCS)

dominant point-based approach

useless match point detection

branch elimination