Finding Longest Common Subsequences: New anytime A* search results

作     者：Djukanovic, Marko Raidl, Guenther R. Blum, Christian 

作者机构：TU Wien Inst Log & Computat Vienna Austria Artificial Intelligence Res Inst IIIA CSIC Campus UAB Bellaterra Spain 

出 版 物：《APPLIED SOFT COMPUTING》 (应用软计算)

年 卷 期：2020年第95卷

页      面：106499-106499页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Doctoral Program "Vienna Graduate School on Computational Optimization'' - Austrian Science Foundation (FWF) [W1260-N35] 

主　　题：Longest common subsequence problem Hybrid metaheuristic A* search Beam search Anytime column search 

摘      要：The Longest Common Subsequence (LCS) problem aims at finding a longest string that is a subsequence of each string from a given set of input strings. This problem has applications, in particular, in the context of bioinformatics, where strings represent DNA or protein sequences. Existing approaches include numerous heuristics, but only a few exact approaches, limited to rather small problem instances. Adopting various aspects from leading heuristics for the LCS, we first propose an exact A* search approach, which performs well in comparison to earlier exact approaches in the context of small instances. On the basis of A* search we then develop two hybrid A*-based algorithms in which classical A* iterations are alternated with beam search and anytime column search, respectively. A key feature to guide the heuristic search in these approaches is the usage of an approximate expected length calculation for the LCS of uniform random strings. Even for large problem instances these anytime A* variants yield reasonable solutions early during the search and improve on them over time. Moreover, they terminate with proven optimality if enough time and memory is given. Furthermore, they yield upper bounds and, thus, quality guarantees when terminated early. We comprehensively evaluate the proposed methods using most of the available benchmark sets from the literature and compare to the current state-of-the-art methods. In particular, our algorithms are able to obtain new best results for 82 out of 117 instance groups. Moreover, in most cases they also provide significantly smaller optimality gaps than other anytime algorithms. (C) 2020 Elsevier B.V. All rights reserved.