On Solving the Multiple Variable Gapped Longest Common Subsequence Problem

Computer Science > Artificial Intelligence [Submitted on 19 Apr 2026] On Solving the Multiple Variable Gapped Longest Common Subsequence Problem Marko Djukanović, Nikola Balaban, Christian Blum, Aleksandar Kartelj, Sašo Džeroski, Žiga Zebec This paper addresses the Variable Gapped Longest Common Subsequence (VGLCS) problem, a generalization of the classical LCS problem involving flexible gap constraints between consecutive solutions' characters. The problem arises in molecular sequence comparison, where structural distance constraints between residues must be respected, and in time-series analysis where events are required to occur within specified temporal delays. We propose a search framework based on the root-based state graph representation, in which the state space comprises a generally large number of rooted state subgraphs. To cope with the resulting combinatorial explosion, an iterative beam search strategy is employed, dynamically maintaining a global pool of promising candidate root nodes, enabling effective control of diversification across iterations. To exploit the search for high-quality solutions, several known heuristics from the LCS literature are utilized into the standalone beam search procedure. To the best of our knowledge, this is the first comprehensive computational study on the VGLCS problem comprising 320 synthetic instances with up to 10 input sequences and up to 500 characters. Experimental results show robustness of the designed approach over the baseline beam search in comparable runtimes. Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2604.18645 [cs.AI]   (or arXiv:2604.18645v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2604.18645 Focus to learn more Submission history From: Marko Djukanovic Dr. [view email] [v1] Sun, 19 Apr 2026 21:44:53 UTC (196 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-04 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)