A Space-Bounded Anytime Algorithm for the Multiple Longest Common Subsequence Problem.
A Space-Bounded Anytime Algorithm for the Multiple Longest Common Subsequence Problem.
复制标题
DOI：
10.1109/tkde.2014.2304464
复制
发表时间：
2014-11
影响因子：
8.9
通讯作者：
Chen G
中科院分区：
文献类型：
--
作者：
Yang J;Xu Y;Shang Y;Chen G
多个最长公共子序列(MLCS)问题涉及到序列相似性的识别，是许多领域中的一个重要问题。作为一个NP-Hard问题，它的精确算法很难处理大规模数据，现实应用中需要时间和空间高效的算法。为了处理时间约束，已经提出了Anytime算法，以在合理的时间内生成良好的解。然而，对于空间效率较高的MLCS算法的研究工作很少。本文将MLCS问题转化为图搜索问题，提出了两种空间高效的随时MLCS算法SA-MLCS和SLA-MLCS。SA-MLCS使用迭代波束加宽搜索策略来减少迭代过程中寻找更好解的空间占用。在SA-MLCS的基础上，提出了一种空间受限算法SLA-MLCS，以避免空间占用超过可用内存。当SA-MLCS达到给定的空间界限时，SLA-MLCS使用替换策略。实验结果表明，SA-MLCS和SLA-MLCS比目前最先进的近似算法MLCS-APP节省了一个数量级的空间和时间，同时找到了更好的解。与最先进的Anytime算法Pro-MLCS、SA-MLCS和SLA-MLCS相比，可以解决一个数量级更大的实例。此外，在大型实例上，SLA-MLCS可以找到比SA-MLCS更好的解决方案。
The multiple longest common subsequence (MLCS) problem, related to the identification of sequence similarity, is an important problem in many fields. As an NP-hard problem, its exact algorithms have difficulty in handling large-scale data and time- and space-efficient algorithms are required in real-world applications. To deal with time constraints, anytime algorithms have been proposed to generate good solutions with a reasonable time. However, there exists little work on space-efficient MLCS algorithms. In this paper, we formulate the MLCS problem into a graph search problem and present two space-efficient anytime MLCS algorithms, SA-MLCS and SLA-MLCS. SA-MLCS uses an iterative beam widening search strategy to reduce space usage during the iterative process of finding better solutions. Based on SA-MLCS, SLA-MLCS, a space-bounded algorithm, is developed to avoid space usage from exceeding available memory. SLA-MLCS uses a replacing strategy when SA-MLCS reaches a given space bound. Experimental results show SA-MLCS and SLA-MLCS use an order of magnitude less space and time than the state-of-the-art approximate algorithm MLCS-APP while finding better solutions. Compared to the state-of-the-art anytime algorithm Pro-MLCS, SA-MLCS and SLA-MLCS can solve an order of magnitude larger size instances. Furthermore, SLA-MLCS can find much better solutions than SA-MLCS on large size instances.