On Solving the Multiple Variable Gapped Longest Common Subsequence Problem

Aleksandar Kartelj; Christian Blum; Marko Djukanovi\'c; Nikola Balaban; Sa\v{s}o D\v{z}eroski; \v{Z}iga Zebec

arxiv: 2604.18645 · v1 · submitted 2026-04-19 · 💻 cs.AI

On Solving the Multiple Variable Gapped Longest Common Subsequence Problem

Marko Djukanovi\'c , Nikola Balaban , Christian Blum , Aleksandar Kartelj , Sa\v{s}o D\v{z}eroski , \v{Z}iga Zebec This is my paper

Pith reviewed 2026-05-10 05:23 UTC · model grok-4.3

classification 💻 cs.AI

keywords variable gapped longest common subsequenceVGLCSbeam searchiterative beam searchlongest common subsequencesequence alignmentcombinatorial searchsynthetic benchmarks

0 comments

The pith

An iterative beam search on root-based state graphs solves the variable gapped longest common subsequence problem more robustly than standard beam search.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a method for the variable gapped longest common subsequence problem, which requires finding common subsequences in multiple sequences while respecting flexible gap constraints between matches. This is relevant for molecular biology to account for structural distances and for time-series to respect temporal windows. The approach uses a root-based state graph to model the problem and applies an iterative beam search that keeps a pool of promising root nodes to manage the large search space across iterations. LCS heuristics are incorporated to guide the search toward high-quality solutions. Tests on 320 synthetic instances show this yields more robust results than a baseline beam search at similar computational cost.

Core claim

The central claim is that modeling the VGLCS problem via a root-based state graph and solving it with an iterative beam search strategy that dynamically maintains a global pool of promising candidate root nodes, while integrating known LCS heuristics, leads to robust performance improvements over baseline beam search on large synthetic test sets.

What carries the argument

The root-based state graph representation, in which states are organized into rooted subgraphs, and the iterative beam search that maintains a global pool of promising root nodes to control diversification across iterations.

If this is right

The framework effectively addresses instances with multiple sequences up to 10 in number and 500 characters each.
Integration of LCS heuristics into the beam search enhances solution quality for the gapped variant.
Comparable runtimes allow practical application without extra computational overhead.
The study on 320 instances provides a benchmark set for evaluating future VGLCS algorithms.
Applications in molecular sequence comparison and time-series analysis can benefit from this search strategy.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The root pool mechanism for diversification may apply to beam search in other sequence or graph problems.
Validation on actual biological or real time-series data would test if the observed robustness transfers beyond synthetics.
Hybrid approaches combining this search with integer programming could solve medium-sized instances exactly.
Extensions to handle even more sequences or longer strings could build on the state graph structure.

Load-bearing premise

The 320 synthetic instances with up to 10 sequences and 500 characters are representative of the structure and difficulty in real molecular or time-series data.

What would settle it

Evaluating the approach on real molecular sequence datasets with verifiable optimal or high-quality VGLCS solutions and comparing performance margins to the baseline.

Figures

Figures reproduced from arXiv: 2604.18645 by Aleksandar Kartelj, Christian Blum, Marko Djukanovi\'c, Nikola Balaban, Sa\v{s}o D\v{z}eroski, \v{Z}iga Zebec.

**Figure 1.** Figure 1: RootedSubspace(u = ((1, 1), 0)) between A BCA and A CAB, assuming G1 = G2 = 1. A final/terminal state is displayed in gray. The white-filled node is a valid LCS node, but not an VGLCS node—the second gap constraint is violated. The longest solution generated from this subspace is ACA. Multi-Source Beam Search. Unlike the classical LCSP, the VGLCSP may exhibit multiple, potentially exponentially many, disco… view at source ↗

**Figure 2.** Figure 2: Root state space subgraphs: disconnected components. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Figure 3: Average solution quality of the three approaches. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: Simplified workflow of the Iterative Multi-source Beam Search (IMSBS). [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗

**Figure 5.** Figure 5: Beam search tuning results on the Random benchmark suite [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

**Figure 6.** Figure 6: IMSBS parameter tuning results on the Random benchmark suite. Numerical results for all three heuristic derivatives are shown in [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗

**Figure 7.** Figure 7: Number of instances for which Bs and Imsbs achieve a specific relative ratio of the obtained solution quality with respect to the known optimal solutions [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a usable iterative beam search for VGLCS plus the first big experiments on instances up to 10 sequences, but the baseline comparison is not clearly isolated.

read the letter

The main point is that this work introduces an iterative beam search on a root-based state graph for the variable gapped longest common subsequence problem and backs it with the first comprehensive experiments on instances with up to 10 sequences and 500 characters each. They model the state space as a set of rooted subgraphs and keep a global pool of promising roots to handle diversification across iterations. Standard LCS heuristics get integrated into the beam search step itself. On the 320 synthetic instances the method shows better robustness than a baseline beam search at similar runtimes. That setup looks like a reasonable practical heuristic for sequence problems with flexible gap constraints, such as molecular comparisons or time-series event detection with delay rules. The framework builds directly on existing LCS ideas without introducing new parameters or fitted models. One soft spot is the baseline. The description says known heuristics from the LCS literature are used in the standalone beam search procedure, yet it does not state whether the baseline beam search includes those same heuristics. If the baseline is a plain version without them, the reported gains could come from the heuristics rather than the iterative root-pool mechanism. That needs explicit clarification to isolate the contribution of the new framework. All testing stays on synthetic data. While the instance sizes mark a step forward from prior work, the absence of any real molecular sequences or actual time-series examples leaves the transfer to the motivating applications unexamined. This paper is for researchers working on heuristic search for generalized LCS problems or combinatorial optimization in bioinformatics. A reader who follows sequence alignment variants or needs practical solvers for gapped subsequence tasks would get value from the framework description and the scale of the experiments. It deserves a serious referee because it supplies the first substantial computational study on VGLCS and the method is a grounded extension of known techniques. I would recommend sending it for peer review, with the expectation that referees will ask for a clearer baseline definition and some discussion of performance on real data.

Referee Report

1 major / 2 minor

Summary. The paper addresses the Variable Gapped Longest Common Subsequence (VGLCS) problem, a generalization of LCS with flexible gap constraints between matching characters. It proposes an iterative beam search framework built on a root-based state graph representation, where the state space is decomposed into rooted subgraphs and a global pool of promising root nodes is maintained across iterations to promote diversification. Known LCS heuristics are incorporated into the beam search procedure. The approach is tested as the first comprehensive computational study on 320 synthetic instances (up to 10 sequences, 500 characters each), with the central claim being greater robustness than a baseline beam search at comparable runtimes.

Significance. If the experimental comparison isolates the framework's contributions, the work would supply a practical heuristic for VGLCS instances arising in molecular biology (residue distance constraints) and time-series analysis (temporal event delays). The evaluation scale of 320 synthetic instances constitutes a clear strength, offering initial evidence of behavior on moderately sized inputs. No machine-checked proofs or parameter-free derivations are present, so significance rests on the empirical robustness claim.

major comments (1)

[Section 5] Section 5 (Experimental Results): the baseline beam search is not described as incorporating the LCS heuristics that the abstract states are 'utilized into the standalone beam search procedure.' If the heuristics are absent from the baseline, observed robustness gains on the 320 instances cannot be attributed to the root-based state graph, global pool maintenance, or iterative diversification rather than the heuristics themselves. Clarification of the exact baseline configuration is required to support the central claim.

minor comments (2)

[Abstract] Abstract: the phrase 'better robustness' would be strengthened by a parenthetical reference to the concrete metric (e.g., average solution length or success rate) used to quantify it.
[Section 3] Section 3 (Problem Definition): an explicit mathematical statement of the variable gap constraints (e.g., lower/upper bounds per pair of consecutive matches) would improve readability for readers outside the immediate LCS community.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and the constructive comment on the experimental section. We agree that the baseline configuration requires explicit clarification to properly attribute the observed robustness gains. We will revise the manuscript accordingly.

read point-by-point responses

Referee: [Section 5] Section 5 (Experimental Results): the baseline beam search is not described as incorporating the LCS heuristics that the abstract states are 'utilized into the standalone beam search procedure.' If the heuristics are absent from the baseline, observed robustness gains on the 320 instances cannot be attributed to the root-based state graph, global pool maintenance, or iterative diversification rather than the heuristics themselves. Clarification of the exact baseline configuration is required to support the central claim.

Authors: We agree with the observation that the manuscript does not explicitly state whether the baseline beam search incorporates the LCS heuristics. In the paper, the phrase 'standalone beam search procedure' refers to the beam search component used inside our iterative framework, where the LCS heuristics are applied. The baseline is a conventional beam search that lacks the root-based state graph representation, global pool of root nodes, and iterative diversification mechanism. To address the concern and strengthen the central claim, we will revise Section 5 to explicitly describe the baseline as not including the LCS heuristics. This will make clear that the comparison evaluates the full proposed approach (framework + heuristics) against a basic beam search. If the referee deems it necessary, we can also add a brief discussion or supplementary experiment isolating the heuristics' contribution, but the current 320-instance results already demonstrate the practical advantage of the combined method at comparable runtimes. revision: yes

Circularity Check

0 steps flagged

No circularity: standard algorithmic proposal validated on new synthetic instances

full rationale

The paper proposes an iterative beam search framework for VGLCS using root-based state graphs and known LCS heuristics. No equations, fitted parameters, or predictions are defined in terms of themselves. The central claim is empirical robustness on 320 new synthetic instances, with no self-citation chains or uniqueness theorems invoked to force the result. The derivation is self-contained as a search algorithm tested against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The method rests on standard assumptions of beam search and LCS dynamic programming; no new free parameters, axioms, or invented entities are introduced beyond the problem definition itself.

axioms (2)

standard math Beam search maintains a fixed-width set of promising partial solutions at each step.
Invoked in the description of the iterative strategy.
domain assumption LCS heuristics can be directly transferred to guide search in the gapped variant.
Stated as utilization of known heuristics from LCS literature.

pith-pipeline@v0.9.0 · 5515 in / 1167 out tokens · 34310 ms · 2026-05-10T05:23:54.097791+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

In: International Conference on Combinatorics on Words

Adamson, D., Kosche, M., Ko , T., Manea, F., Siemer, S.: Longest common subsequence with gap constraints. In: International Conference on Combinatorics on Words. pp. 60--76. Springer (2023)

work page 2023
[2]

Discrete Applied Mathematics 158(12), 1315--1324 (2010)

Adi, S.S., Braga, M.D., Fernandes, C.G., Ferreira, C.E., Martinez, F.V., Sagot, M.F., Stefanes, M.A., Tjandraatmadja, C., Wakabayashi, Y.: Repetition-free longest common subsequence. Discrete Applied Mathematics 158(12), 1315--1324 (2010)

work page 2010
[3]

In: Proceedings Seventh International Symposium on String Processing and Information Retrieval

Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000. pp. 39--48. IEEE (2000)

work page 2000
[4]

Blum, C., Festa, P.: Metaheuristics for String Problems in Bio-informatics, vol. 6. John Wiley & Sons (2016)

work page 2016
[5]

Applied Soft Computing 95, 106499 (2020)

Djukanovic, M., Raidl, G., Blum, C.: Finding longest common subsequences: New anytime A* search results. Applied Soft Computing 95, 106499 (2020)

work page 2020
[6]

Information Sciences 295, 247--257 (2015)

Farhana, E., Rahman, M.S.: Constrained sequence analysis algorithms in computational biology. Information Sciences 295, 247--257 (2015)

work page 2015
[7]

Journal of Discrete Algorithms 2(2), 257--270 (2004)

Jiang, T., Lin, G., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. Journal of Discrete Algorithms 2(2), 257--270 (2004)

work page 2004
[8]

Neural computation 27(3), 594--614 (2015)

Lainscsek, C., Sejnowski, T.J.: Delay differential analysis of time series. Neural computation 27(3), 594--614 (2015)

work page 2015
[9]

Computers & Operations Research 39(3), 512--520 (2012)

Mousavi, S.R., Tabataba, F.: An improved algorithm for the longest common subsequence problem. Computers & Operations Research 39(3), 512--520 (2012)

work page 2012
[10]

In: Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan

Penga, Y.H., Yangb, C.B.: The longest common subsequence problem with variable gapped constraints. In: Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan. pp. 17--23 (2011)

work page 2011
[11]

Blum and P

C. Blum and P. Festa, Metaheuristics for String Problems in Bio-informatics , Vol. 6, John Wiley & Sons, 2016

work page 2016
[12]

Penga and C.-B

Y.-H. Penga and C.-B. Yangb, The Longest Common Subsequence Problem with Variable Gapped Constraints, In Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan , pp. 17--23, 2011

work page 2011
[13]

International Conference on Combinatorics on Words , pages=

Longest common subsequence with gap constraints , author=. International Conference on Combinatorics on Words , pages=. 2023 , organization=

work page 2023
[14]

Neural computation , volume=

Delay differential analysis of time series , author=. Neural computation , volume=. 2015 , publisher=

work page 2015
[15]

Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan , pages=

The Longest Common Subsequence Problem with Variable Gapped Constraints , author=. Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan , pages=

work page
[16]

International Conference on Combinatorial Optimization and Applications , pages=

The longest subsequence-repeated subsequence problem , author=. International Conference on Combinatorial Optimization and Applications , pages=. 2023 , organization=

work page 2023
[17]

Applied Soft Computing , volume =

Djukanovic, Marko and Raidl, Guenther, and Blum, Christian , title =. Applied Soft Computing , volume =. 2020 , issn =

work page 2020
[18]

Journal of Discrete Algorithms , volume=

The longest common subsequence problem for arc-annotated sequences , author=. Journal of Discrete Algorithms , volume=. 2004 , publisher=

work page 2004
[19]

Discrete Applied Mathematics , volume=

Repetition-free longest common subsequence , author=. Discrete Applied Mathematics , volume=. 2010 , publisher=

work page 2010
[20]

Computers & Operations Research , volume=

An improved algorithm for the longest common subsequence problem , author=. Computers & Operations Research , volume=. 2012 , publisher=

work page 2012
[21]

Information Sciences , volume=

Constrained sequence analysis algorithms in computational biology , author=. Information Sciences , volume=. 2015 , publisher=

work page 2015
[22]

2016 , publisher=

Metaheuristics for String Problems in Bio-informatics , author=. 2016 , publisher=

work page 2016

[1] [1]

In: International Conference on Combinatorics on Words

Adamson, D., Kosche, M., Ko , T., Manea, F., Siemer, S.: Longest common subsequence with gap constraints. In: International Conference on Combinatorics on Words. pp. 60--76. Springer (2023)

work page 2023

[2] [2]

Discrete Applied Mathematics 158(12), 1315--1324 (2010)

Adi, S.S., Braga, M.D., Fernandes, C.G., Ferreira, C.E., Martinez, F.V., Sagot, M.F., Stefanes, M.A., Tjandraatmadja, C., Wakabayashi, Y.: Repetition-free longest common subsequence. Discrete Applied Mathematics 158(12), 1315--1324 (2010)

work page 2010

[3] [3]

In: Proceedings Seventh International Symposium on String Processing and Information Retrieval

Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000. pp. 39--48. IEEE (2000)

work page 2000

[4] [4]

Blum, C., Festa, P.: Metaheuristics for String Problems in Bio-informatics, vol. 6. John Wiley & Sons (2016)

work page 2016

[5] [5]

Applied Soft Computing 95, 106499 (2020)

Djukanovic, M., Raidl, G., Blum, C.: Finding longest common subsequences: New anytime A* search results. Applied Soft Computing 95, 106499 (2020)

work page 2020

[6] [6]

Information Sciences 295, 247--257 (2015)

Farhana, E., Rahman, M.S.: Constrained sequence analysis algorithms in computational biology. Information Sciences 295, 247--257 (2015)

work page 2015

[7] [7]

Journal of Discrete Algorithms 2(2), 257--270 (2004)

Jiang, T., Lin, G., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. Journal of Discrete Algorithms 2(2), 257--270 (2004)

work page 2004

[8] [8]

Neural computation 27(3), 594--614 (2015)

Lainscsek, C., Sejnowski, T.J.: Delay differential analysis of time series. Neural computation 27(3), 594--614 (2015)

work page 2015

[9] [9]

Computers & Operations Research 39(3), 512--520 (2012)

Mousavi, S.R., Tabataba, F.: An improved algorithm for the longest common subsequence problem. Computers & Operations Research 39(3), 512--520 (2012)

work page 2012

[10] [10]

In: Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan

Penga, Y.H., Yangb, C.B.: The longest common subsequence problem with variable gapped constraints. In: Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan. pp. 17--23 (2011)

work page 2011

[11] [11]

Blum and P

C. Blum and P. Festa, Metaheuristics for String Problems in Bio-informatics , Vol. 6, John Wiley & Sons, 2016

work page 2016

[12] [12]

Penga and C.-B

Y.-H. Penga and C.-B. Yangb, The Longest Common Subsequence Problem with Variable Gapped Constraints, In Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan , pp. 17--23, 2011

work page 2011

[13] [13]

International Conference on Combinatorics on Words , pages=

Longest common subsequence with gap constraints , author=. International Conference on Combinatorics on Words , pages=. 2023 , organization=

work page 2023

[14] [14]

Neural computation , volume=

Delay differential analysis of time series , author=. Neural computation , volume=. 2015 , publisher=

work page 2015

[15] [15]

Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan , pages=

The Longest Common Subsequence Problem with Variable Gapped Constraints , author=. Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan , pages=

work page

[16] [16]

International Conference on Combinatorial Optimization and Applications , pages=

The longest subsequence-repeated subsequence problem , author=. International Conference on Combinatorial Optimization and Applications , pages=. 2023 , organization=

work page 2023

[17] [17]

Applied Soft Computing , volume =

Djukanovic, Marko and Raidl, Guenther, and Blum, Christian , title =. Applied Soft Computing , volume =. 2020 , issn =

work page 2020

[18] [18]

Journal of Discrete Algorithms , volume=

The longest common subsequence problem for arc-annotated sequences , author=. Journal of Discrete Algorithms , volume=. 2004 , publisher=

work page 2004

[19] [19]

Discrete Applied Mathematics , volume=

Repetition-free longest common subsequence , author=. Discrete Applied Mathematics , volume=. 2010 , publisher=

work page 2010

[20] [20]

Computers & Operations Research , volume=

An improved algorithm for the longest common subsequence problem , author=. Computers & Operations Research , volume=. 2012 , publisher=

work page 2012

[21] [21]

Information Sciences , volume=

Constrained sequence analysis algorithms in computational biology , author=. Information Sciences , volume=. 2015 , publisher=

work page 2015

[22] [22]

2016 , publisher=

Metaheuristics for String Problems in Bio-informatics , author=. 2016 , publisher=

work page 2016