[Back]

M. Djukanovic, C. Berger, G. Raidl, C. Blum:
"On Solving a Generalized Constrained Longest Common Subsequence Problem";
Talk: International Conference on Optimization and Applications, Moscow, Russia; 2020-09-28 - 2020-10-02; in: "International Conference on Optimization and Applications-OPTIMA2020", LNCS / Springer, 12422 (2020), ISBN: 978-3-030-62866-6; 55 - 70.

Given a set of two input strings and a pattern string, the
constrained longest common subsequence problem deals with finding a
longest string that is a subsequence of both input strings and that contains
the given pattern string as a subsequence. This problem has various
applications, especially in computational biology. In this work we consider
the NP-hard case of the problem in which more than two input
strings are given. First, we adapt an existing A
∗
search from two input
strings to an arbitrary number m of input strings (m ≥ 2). With the aim
of tackling large problem instances approximately, we additionally propose
a greedy heuristic and a beam search. All three algorithms are compared
to an existing approximation algorithm from the literature. Beam
search turns out to be the best heuristic approach, matching almost all
optimal solutions obtained by A
∗
search for rather small instances.

http://dx.doi.org/10.1007/978-3-030-62867-3_5

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