[Back]

M. Djukanovic, C. Berger, G. Raidl, C. Blum:
"An A∗Search Algorithm for the Constrained Longest Common Subsequence Problem";
Information Processing Letters, 166 (2020), 1 - 10.

The constrained longest common subsequence (CLCS) problem was introduced as a specific measure of similarity between molecules.It is a special case of the constrained sequence alignment problem and of the longest common subsequence (LCS) problem, whichare both well-studied problems in the scientific literature. Finding similarities between sequences plays an important role in the fieldsof molecular biology, gene recognition, pattern matching, text analysis, and voice recognition, among others. The CLCS problemin particular represents an interesting measure of similarity for molecules that have a putative structure in common. This paperproposes an exact A∗search algorithm for effectively solving the CLCS problem. This A∗search is guided by a tight upper boundcalculation for the cost-to-go for the LCS problem. Our computational study shows that on various artificial and real benchmark setsthis algorithm scales better with growing instance size and requires significantly less computation time to prove optimality thanearlier state-of-the-art approaches from the literature.

http://dx.doi.org/10.1016/j.ipl.2020.106041

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