On Solving the Multiple Variable Gapped Longest Common Subsequence Problem

A research team including Marko Djukanović, Nikola Balaban, Christian Blum, Aleksandar Kartelj, Sašo Džeroski, and Žiga Zebec has published a paper titled "On Solving the Multiple Variable Gapped Longest Common Subsequence Problem" on arXiv. The paper addresses the Variable Gapped Longest Common Subsequence (VGLCS) problem, which generalizes the classical Longest Common Subsequence (LCS) problem by introducing flexible gap constraints between consecutive characters in the solution. This problem has practical applications in molecular sequence comparison, where structural distance constraints between residues must be respected, and in time-series analysis where events must occur within specified temporal delays.

The researchers propose a search framework based on a root-based state graph representation, where the state space comprises numerous rooted state subgraphs. To manage the combinatorial explosion inherent in such problems, they employ an iterative beam search strategy that dynamically maintains a global pool of promising candidate root nodes. This approach allows for effective control of diversification across iterations. The method incorporates several known heuristics from LCS literature into the standalone beam search procedure to enhance solution quality. The study represents the first comprehensive computational investigation of the VGLCS problem, evaluating 320 synthetic instances with up to 10 input sequences and up to 500 characters each. Experimental results demonstrate the robustness of their designed approach compared to baseline beam search methods while maintaining comparable runtime performance.