A fast and memory efficient MLCS algorithm by character merging for DNA sequences alignment
A fast and memory efficient MLCS algorithm by character merging for DNA sequences alignment
复制标题
通过字符合并进行 DNA 序列比对的快速且内存高效的 MLCS 算法
DOI：
10.1093/bioinformatics/btz725
复制
发表时间：
2020-02-15
期刊：
影响因子：
5.8
通讯作者：
Wei, Shiwei
中科院分区：
文献类型：
--
作者：
Liu, Sen;Wang, Yuping;Wei, Shiwei
动机
MOTIVATION
Multiple Longest Common Subsequence (MLCS) problem is searching all longest common subsequences of multiple character sequences. It appears in many fields such as data mining, DNA alignment, bioinformatics, text editing and so on. With the increasing of sequence length and number of sequences, the existing dynamic programming algorithms and the dominant point based algorithms become ineffective and inefficient, especially for large-scale MLCS problems.
RESULTS
In this paper, by considering the characteristics of DNA sequences with many consecutively repeated characters, we first design a character merging scheme which merges the consecutively repeated characters in the sequences. As a result, it shortens the length of sequences considered and saves the space of storing all sequences. To further reduce the space and time costs, we construct a Weighted Directed Acyclic Graph (WDAG) which is much smaller than widely used DAG for MLCS problems. Based on these techniques, we propose a fast and memory efficient algorithm for MLCS problems. Finally, the experiments are conducted and the proposed algorithm is compared with several state-of-the art algorithms. The experimental results show that the proposed algorithm performs better than the compared state-of-the art algorithms in both time and space costs.