Details

Autor(en) / Beteiligte

• Djukanovic, Marko
• Raidl, Günther R.
• Blum, Christian

Titel

Anytime algorithms for the longest common palindromic subsequence problem

Ist Teil von

• Computers & operations research, 2020-02, Vol.114, p.104827, Article 104827

Ort / Verlag

New York: Elsevier Ltd

Erscheinungsjahr

2020

Quelle

Elsevier ScienceDirect Journals

Beschreibungen/Notizen

• •We propose a novel anytime A* algorithm which is a hybrid of A* search and Anytime Column Search (A* + ACS).•A* + ACS is able to solve small to medium-sized LCPS instances to proven optimality.•We derive a novel heuristic estimation that approximates the expected length of an LCPS.•A* + ACS is the state-of-the-art approach for the LCPS problem concerning final solution quality and final remaining optimality gap.•Overall the anytime-behavior of the A* + ACS is superior to the one of the other approaches. The longest common palindromic subsequence (LCPS) problem aims at finding a longest string that appears as a subsequence in each of a set of input strings and is a palindrome at the same time. The problem is a special variant of the well known longest common subsequence problem and has applications in particular in genomics and biology, where strings correspond to DNA or protein sequences and similarities among them shall be detected or quantified. We first present a more traditional A* search that makes use of an advanced upper bound calculation for partial solutions. This exact approach works well for instances with two input strings and, as shown in experiments, outperforms several other exact methods from the literature. However, the A* search also has natural limitations when a larger number of strings shall be considered due to the problem’s complexity. To effectively deal with this case in practice, anytime A* search variants are investigated, which are able to return a reasonable heuristic solution at almost any time and are expected to find better and better solutions until reaching a proven optimum when enough time given. In particular a novel approach is proposed in which Anytime Column Search (ACS) is interleaved with traditional A* node expansions. The ACS iterations are guided by a new heuristic function that approximates the expected length of an LCPS in subproblems usually much better than the available upper bound calculation. This A*+ACS hybrid is able to solve small to medium-sized LCPS instances to proven optimality while returning good heuristic solutions together with upper bounds for large instances. In rigorous experimental evaluations we compare A*+ACS to several other anytime A* search variants and observe its superiority.