.png){kind=icon}
返回
A Novel Key Point Based MLCS Algorithm for Big Sequences Mining
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2024.3485234.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Mining multiple longest common subsequences (MLCS) from a set of sequences of length three or more over a finite alphabet (a classical NP-hard problem) is an important task in many fields, e.g., bioinformatics, computational genomics, pattern recognition, information extraction, etc. Applications in these fields often involve generating very long sequences (length >= 10,000), referred to as big sequences. Despite efforts in improving the time and space complexities of MLCS mining algorithms, both existing exact and approximate algorithms face challenges in handling big sequences due to the overwhelming size of their problem-solving graph model MLCS-DAG (Directed Acyclic Graph), leading to the issue of memory explosion or extremely high time complexity. To bridge the gap, this paper first proposes a new identification and deletion strategy for different classes of non-critical points in the mining of MLCS, which are the points that do not contribute to their MLCSs mining in the MLCS-DAG. It then proposes a new MLCS problem-solving graph model, namely DAG(KP) (a new MLCS-DAG containing only Key Points). A novel parallel MLCS algorithm, called KP-MLCS (Key Point based MLCS), is also presented, which can mine and compress all MLCSs of big sequences effectively and efficiently. Extensive experiments on both synthetic and real-world biological sequences show that the proposed algorithm KP-MLCS drastically outperforms the existing state-of-the-art MLCS algorithms in terms of both efficiency and effectiveness.
Keyword:
Approximation algorithms
Parallel algorithms
Problem-solving
Finite element analysis
Directed acyclic graph
Data mining
NP-hard problem
Heuristic algorithms
Face recognition
MLCS (Multiple longest common subsequence)
Explosions
MLCS-DAG (Directedacyclic graph)
DAG(KP) (a new MLCS-DAG containing only key points)
non-critical points
KP-MLCS (Key point based MLCS)
non-critical points
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
分享收藏
A parallel naive approach for non-dominated sorting: a theoretical study considering PRAM CREW model.png)
SOFT COMPUTING
SOFT COMPUTINGIF2.5
PREAI
分享收藏A branch and bound irredundant graph algorithm for large-scale MLCS problemsPATTERN RECOGNITION
PATTERN RECOGNITIONIF7.6
PREAI
分享收藏
查看更多内容