On Solving the Multiple Variable Gapped Longest Common Subsequence Problem

• URL: http://arxiv.org/abs/2604.18645v1
• Date: Sun, 19 Apr 2026 21:44:53 GMT
• Title: On Solving the Multiple Variable Gapped Longest Common Subsequence Problem
• Abstract summary: This paper addresses the Variable Gapped Longest Common Subsequence problem.<n>It is a generalization of the classical LCS problem involving flexible gap constraints between consecutive solutions' characters.<n>We propose a search framework based on the root-based state graph representation.
• Score: 36.85666459036717
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Neuro-Evolved Heuristics for Variable Gapped Common Subsequence Identification [40.920500181764986]
  This study addresses the Variable Gapped Longest Common Subsequence Problem (VGLCSP)<n>VGLCSP is a variant of the classical longest common subsequence problem with additional gap constraints.<n>We propose a learning-based approach for automatically designing more effective data-driven robustnesss.
  arXiv  Detail & Related papers  (2026-08-01T22:36:35Z)
• Regularized Large Neighborhood Search [11.54620327711825]
  Operations research practitioners typically tackle NP-hard problems using large neighborhood search (LNS)<n>We bridge this gap by regularized LNS (RLNS)<n>Undertropic regularization, we prove that RLNS performs exact block Gibbs sampling.
  arXiv  Detail & Related papers  (2026-06-01T14:16:18Z)
• A Learning Search Algorithm for the Restricted Longest Common Subsequence Problem [40.64116457007417]
  The Restricted Longest Common Subsequence (RLCS) problem has significant applications in bioinformatics. This paper introduces two novel approaches designed to enhance the search process by steering it towards promising regions. An important contribution of this paper is found in the generation of real-world instances where scientific abstracts serve as input strings.
  arXiv  Detail & Related papers  (2024-10-15T20:02:15Z)
• Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models [61.10851158749843]
  Key insights can be obtained by discovering lead-lag relationships inherent in the data. We develop a clustering-driven methodology for robust detection of lead-lag relationships in lagged multi-factor models.
  arXiv  Detail & Related papers  (2023-05-11T10:30:35Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. Experiments show that the pruning brought by this caching mechanism allows significantly reducing the number of nodes expanded by the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T10:18:33Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
  We consider causal discovery in continuous-time for the study of dynamical systems. We propose a causal discovery algorithm based on penalized Neural ODEs.
  arXiv  Detail & Related papers  (2021-05-06T08:48:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.