A Biased Random Key Genetic Algorithm for Solving the Longest Common Square Subsequence Problem

Abstract

This paper considers the longest common square subsequence (LCSqS) problem, a variant of the longest common subsequence (LCS) problem in which solutions must be square strings. A square string can be expressed as the concatenation of a string with itself. The LCSqS problem has applications in bioinformatics, for discovering internal similarities between molecular structures. We propose a metaheuristic approach, a biased random key genetic algorithm (BRKGA) hybridized with a beam search from the literature. Our approach is based on reducing the LCSqS problem to a set of promising LCS problems. This is achieved by cutting each input string into two parts first and then evaluating such a transformed instance by solving the LCS problem for the obtained overall set of strings. The task of the BRKGA is, hereby, to find a set of good cut points for the input strings. For this purpose, the search is carefully biased by problem-specific greedy information. For each cut point vector, the resulting LCS problem is approximately solved by the existing beam search approach. The proposed algorithm is evaluated against a previously proposed state-of-the-art variable neighborhood search (VNS) on random uniform instances from the literature, new non-uniform instances, and a real-world instance set consisting of DNA strings. The results underscore the importance of our work, as our novel approach outperforms former state-of-the-art with statistical significance. Particularly, they evidence the limitations of the VNS when solving non-uniform instances, for which our method shows superior performance.