Proceedings of the
The Nineteenth International Conference on Computational Intelligence and Security (CIS 2023)
December 1 – 4, 2023, Haikou, China
A Novel Directed Acyclic Graph-based Hierarchical Propulsion (DAG-HP) Algorithm for MLCS Problem
1School of Computer Science and Engineering, Guilin University of Aerospace Technology, China.
2School of Computer Science, Xi'an Polytechnic University, China.
ABSTRACT
Finding the longest common subsequences of many sequences on a symbol set(usually called the Multiple Longest Common Subsequence, shortly for the MLCS problem) is a fundamental and challenging issue in the data mining field such as DNA and protein sequences alignment and disease surveillance. The existing MLCS algorithms are not suitable to solve the large-scale MLCS problem because of the long runtime and huge memory consumption. To address this issue, in this paper, a novel Directed Acyclic Graph-based Hierarchical Propulsion (DAG-HP) algorithm is designed, which first transforms the problem of finding MLCS from sequences into determining the longest paths in the DAG and then finds the longest paths in the DAG that correspond to the MLCSs. Experimental comparisons with the existing dominant-point-based MLCS algorithms show that the proposed DAG-HP algorithm can efficiently solve the large-scale MLCS problem with much less runtime and memory consumption.
Keywords: Multiple Longest Common Subsequences (MLCS), Match point, Dominant point method, Directed acyclic graph.
Download PDF
1School of Computer Science and Engineering, Guilin University of Aerospace Technology, China.
2School of Computer Science, Xi'an Polytechnic University, China.
ABSTRACT
Finding the longest common subsequences of many sequences on a symbol set(usually called the Multiple Longest Common Subsequence, shortly for the MLCS problem) is a fundamental and challenging issue in the data mining field such as DNA and protein sequences alignment and disease surveillance. The existing MLCS algorithms are not suitable to solve the large-scale MLCS problem because of the long runtime and huge memory consumption. To address this issue, in this paper, a novel Directed Acyclic Graph-based Hierarchical Propulsion (DAG-HP) algorithm is designed, which first transforms the problem of finding MLCS from sequences into determining the longest paths in the DAG and then finds the longest paths in the DAG that correspond to the MLCSs. Experimental comparisons with the existing dominant-point-based MLCS algorithms show that the proposed DAG-HP algorithm can efficiently solve the large-scale MLCS problem with much less runtime and memory consumption.
Keywords: Multiple Longest Common Subsequences (MLCS), Match point, Dominant point method, Directed acyclic graph.
Download PDF