[Zurück]

M. Djukanovic, G. Raidl, C. Blum:
"Finding Longest Common Subsequences: New anytime A search results";
Applied Soft Computing, 95 (2020), S. 1 - 21.

TheLongestCommonSubsequence(LCS)problemaimsatfindingalongeststringthatisasubsequenceof each string from a given set of input strings. This problem has applications, in particular, in thecontext of bioinformatics, where strings represent DNA or protein sequences. Existing approachesinclude numerous heuristics, but only a few exact approaches, limited to rather small probleminstances. Adopting various aspects from leading heuristics for the LCS, we first propose an exact A∗searchapproach,whichperformswellincomparisontoearlierexactapproachesinthecontextofsmallinstances.OnthebasisofA∗searchwethendeveloptwohybridA∗-basedalgorithmsinwhichclassicalA∗iterations are alternated with beam search and anytime column search, respectively. A key featureto guide the heuristic search in these approaches is the usage of an approximate expected lengthcalculation 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 yieldupper bounds and, thus, quality guarantees when terminated early. We comprehensively evaluate theproposed methods using most of the available benchmark sets from the literature and compare tothe current state-of-the-art methods. In particular, our algorithms are able to obtain new best resultsfor 82 out of 117 instance groups. Moreover, in most cases they also provide significantly smalleroptimality gaps than other anytime algorithms.

http://dx.doi.org/10.1016/j.asoc.2020.106499

https://publik.tuwien.ac.at/files/publik_293653.pdf