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

Christian Blum; Pedro Pinacho-Davidson

REVIEW 4 major objections 4 minor 1 cited by

The paper claims that a biased random-key genetic algorithm with a fast decoder now produces the best known solutions to the longest run subsequence problem.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

A BRKGA with an efficient random-key decoder is reported to beat MMAS and CPLEX on the NP-hard longest run subsequence problem, though large-alphabet instances still need improvement.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection A plausible BRKGA for LRS with a fast decoder, but the SOTA claim rests on CPLEX and a self-made MMAS; full text is corrupted, so the empirical case can't be verified. the 4 major comments →

arxiv 2508.14020 v1 pith:IWJPB2SK submitted 2025-08-19 cs.AI cs.DM

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

Christian Blum , Pedro Pinacho-Davidson This is my paper

classification cs.AI cs.DM

keywords longest run subsequencebiased random-key genetic algorithmMax-Min Ant Systemgenome reassemblyNP-hard combinatorial optimizationmetaheuristicsstring algorithms

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

The longest run subsequence (LRS) problem asks for the longest subsequence of a string that is built from consecutive runs of equal characters; it is NP-hard and appears in genome reassembly. The paper tries to show that a biased random-key genetic algorithm (BRKGA), designed so that evaluating an individual means decoding a vector of gray values into a valid LRS solution, is currently the strongest heuristic for this problem. The authors compare it against a Max-Min Ant System they implemented and against the CPLEX integer programming solver on the same benchmark instances, and claim BRKGA matches or beats both within the allowed time. They also acknowledge that results on large-alphabet strings still leave room for improvement. If true, the work provides a practical way to get good LRS solutions on instances where exact solving is too slow.

Core claim

The central claim is that a BRKGA is currently a state-of-the-art technique for the LRS problem. The contribution is a decoding scheme that converts vectors of gray values into valid LRS solutions quickly, so that evolutionary search can evaluate a large number of individuals in a reasonable time. On the tested instances, this approach outperforms or ties the Max-Min Ant System and CPLEX within the same budget, while the authors note that large alphabet sizes are still a weak spot.

What carries the argument

A biased random-key genetic algorithm: each individual is a vector of random keys (gray values), and a deterministic decoder turns that vector into a valid LRS solution; the search then biases recombination toward elite individuals. The decoder's speed is what carries the argument, because it makes the fitness landscape cheap to evaluate and lets the genetic algorithm do many more evaluations than the ant system or exact solver.

Load-bearing premise

The decoder that turns random-key vectors into LRS solutions is assumed to be fast and able to reach every good solution; if it restricts the search space or becomes too slow, the method's edge over other solvers would disappear.

What would settle it

Set CPLEX, the Max-Min Ant System, and BRKGA on a held-out set of large-alphabet LRS instances with identical time budgets; if either baseline returns longer subsequences on most instances, the state-of-the-art claim fails. Alternatively, time the decoder alone: if its runtime grows steeply with string length, the efficiency premise fails even if the reported instances are won.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

On the benchmark suite used, BRKGA finds LRS solutions at least as good as those from the Max-Min Ant System and CPLEX under the same time budget.
The fast decoder makes evolutionary search practical for LRS instances where exact integer programming cannot finish quickly.
Large-alphabet strings remain the hardest cases, so gains over the alternatives are smaller there.
The Max-Min Ant System built for comparison provides a reproducible baseline for future LRS heuristics.

Where Pith is reading between the lines

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

The same decoder idea could transfer to other run-based or subsequence problems where evaluation cost dominates the search.
A natural next experiment is to combine BRKGA with a local-search decoder on large-alphabet instances to close the reported gap.
Because the random-key encoding is generic, the template could be dropped into genome reassembly pipelines that formulate their core matching step as an LRS instance.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

A plausible BRKGA for LRS with a fast decoder, but the SOTA claim rests on CPLEX and a self-made MMAS; full text is corrupted, so the empirical case can't be verified.

read the letter

Quick take: the paper is a solid application of BRKGA to the Longest Run Subsequence problem, with an efficient decoder as the main technical idea. But I cannot verify the details because the supplied full text is corrupted (mojibake plus a stray header from arXiv:2508.14019). So this is an abstract-level read. On that basis, the abstract makes a strong claim — BRKGA is 'currently a state-of-the-art technique for the LRS problem' — but the evidence reported is thin: two comparators, CPLEX and a Max-Min Ant System developed for this paper. CPLEX is a serious exact solver, so beating it on the tested instances is meaningful, but CPLEX is not an LRS-specific solver and exact methods often scale poorly; being better than CPLEX on a heuristic time budget is not the same as being state of the art. The MMAS is a new baseline, not a published prior heuristic. The abstract does not name any existing LRS solver, does not report statistics or instance provenance, and does not state hyperparameters or time budgets. That is the load-bearing soft spot.

What the paper does well: the decoder idea — converting gray-value random keys into valid solutions — is genuinely interesting and could be the real contribution. If the decoder is both fast and complete (or at least does not distort the landscape), that is a useful template for other subsequence problems. The paper also openly flags that large-alphabet instances remain hard, which is an honest limitation. The problem itself, LRS in genome reassembly, is legitimate and the heuristic comparison is a reasonable first cut.

My overall sense: the empirical SOTA claim overreaches relative to the evidence in the abstract. The paper would be stronger if it compared against the best published LRS heuristics and reported multiple runs with variance. The corrupted full text prevents me from checking whether that evidence exists in the body. If the full text is intact, this deserves a serious referee; if the comparison set is just CPLEX and MMAS, the SOTA sentence should be softened to 'competitive with' or 'outperforms these baselines.'

Who is this for: someone working on subsequence optimization or BRKGA decoders. It is not a field-shifting paper. I would not cite it in the next year unless I was writing specifically about LRS. Reading group: maybe, if the group has a taste for metaheuristic engineering. Recommendation: send it to peer review, but flag the SOTA claim and require comparisons to existing LRS solvers and statistical support.

Referee Report

4 major / 4 minor

Summary. The manuscript proposes a Biased Random Key Genetic Algorithm (BRKGA) for the NP-hard Longest Run Subsequence (LRS) problem. The claimed novelty is a decoder that maps random-key vectors of gray values into valid LRS solutions, with an emphasis on computational efficiency of fitness evaluation. For comparison, the authors implement a Max-Min Ant System (MMAS) and apply the ILP solver CPLEX to all instances. The abstract concludes that the proposed BRKGA is 'currently a state-of-the-art technique' for LRS, while also acknowledging weaker performance on large alphabet sizes. The supplied full text is heavily corrupted, so the actual derivation, tables, and experimental details are largely inaccessible; my assessment is therefore based on the abstract, the visible fragments, and the reader's report.

Significance. If the claims hold, the paper would provide a practical heuristic for an NP-hard bioinformatics-motivated problem and would demonstrate a reusable random-key decoding scheme. The inclusion of an MMAS comparator and CPLEX exact results is a useful experimental scaffold. However, the evidence visible in the manuscript is not sufficient to support the central state-of-the-art claim: the comparison set is narrow, no prior best heuristic is identified, and statistical support is absent.

major comments (4)

[Abstract, final sentence] The claim that BRKGA is 'currently a state-of-the-art technique' is supported only by comparisons with a self-implemented MMAS and CPLEX. No existing LRS heuristic or exact solver from the literature is benchmarked, and no instance provenance or prior best-known results are given. Since MMAS is also designed and implemented in this paper, the comparison is between two new heuristics plus a generic exact solver. This does not establish state of the art; at most it shows outperformance on an unreported test suite. The authors should compare against the best published LRS solver or, failing that, rephrase the claim to 'best among the methods tested here'.
[Experimental section (corrupted full text)] The experimental protocol is not verifiable from the supplied text. Hyperparameters for BRKGA and MMAS, termination criteria, CPLEX version, time budgets, hardware, and number of independent runs are not clearly reported. Heuristic comparisons require multiple seeds/runs and measures of variance; without these, differences could be noise. The visible parameter-like fragments are insufficient for replication. A revision must include a complete table of parameter settings, budgets, and per-instance results, plus a reproducibility statement (code/instances).
[Decoder description] The paper's central methodological assumption is that decoding gray-value vectors into valid LRS solutions is both fast and non-restrictive. No completeness argument or complexity bound for the decoder is visible in the readable parts of the manuscript. If the decoder cannot represent every LRS solution (or every near-optimal one), the BRKGA search operates on a restricted subspace, and the empirical winners would not justify a general state-of-the-art claim. The authors should state whether the decoder is complete, or provide an explicit coverage/reachability analysis (e.g., by testing whether an optimal solution can be embedded in the random-key representation).
[Full text quality] The submitted full text is largely unreadable: it consists of mojibake and includes an unrelated arXiv identifier ('arXiv:2508.14019v1 [astro-ph.CO]') in the header. As a result, the problem formulation, algorithm listings, tables, figures, and proofs could not be checked. This is a load-bearing problem because the experimental evidence for the central claim is inaccessible. The authors must resubmit a clean, well-formatted manuscript; a corrupted PDF/text cannot undergo normal peer review.

minor comments (4)

[Abstract] The phrase 'state-of-the-art technique' should be qualified in the abstract itself, e.g., 'state of the art among the methods tested on our instance suite' or similar, especially given the stated weakness on large alphabets.
[Abstract] The term 'gray values' is nonstandard. It should be defined in the introduction or renamed to, e.g., 'random-key values' to avoid confusion with image-processing terminology.
[Experimental section] The CPLEX comparison should state the ILP formulation used, the CPLEX version, and whether a time limit was imposed. Without this, the exact-solver comparison is uninterpretable.
[Conclusion] The large-alphabet limitation mentioned in the abstract should be discussed in more detail in the conclusion, including possible remedies such as alphabet reduction or problem-specific decoders.

Circularity Check

0 steps flagged

No significant circularity: the BRKGA result is assessed against CPLEX and a separately implemented MMAS; the SOTA claim is empirical, not derived from its own inputs.

full rationale

The paper's central claim is that the proposed BRKGA is currently a state-of-the-art technique for the LRS problem. This claim is supported by computational comparison against CPLEX, an independent exact ILP solver, and against a Max-Min Ant System developed separately for comparison. Nothing in the abstract or readable portions of the text defines the BRKGA's objective or decoding procedure in terms of the benchmark results, and no fitted parameter is relabeled as a prediction. The decoder that maps gray-value vectors to valid solutions is an algorithmic component, not a self-referential derivation: its quality is judged externally by solution quality on test instances. No load-bearing self-citation chain is visible, and no equation in the supplied text reduces a claimed output to an input by construction. The weakness that the SOTA claim rests only on CPLEX and a self-implemented MMAS, with no independent published LRS baseline, is a matter of empirical support and benchmark selection, not circularity. Accordingly, no circular steps are identified.

Axiom & Free-Parameter Ledger

3 free parameters · 3 axioms · 0 invented entities

The paper introduces one algorithmic device, the gray-value decoding map, which is a procedure rather than an entity. The central empirical comparison rests on unstated hyperparameters, instance choices, and the completeness of the decoder.

free parameters (3)

BRKGA hyperparameters (population size, elite fraction, mutation probability, generations) = not stated in abstract
The SOTA result is comparative and depends on these values; without a tuning protocol the advantage may reflect parameter choice.
MMAS hyperparameters (pheromone decay, ant count, iteration limit) = not stated in abstract
The ant system is the main baseline; relative quality is sensitive to how well each algorithm is tuned.
Time budget or termination criterion for CPLEX and heuristics = not stated in abstract
Heuristic versus exact comparisons only establish SOTA if all methods get comparable computational budgets.

axioms (3)

domain assumption LRS is NP-hard and arises in genome reassembly.
Taken from prior literature; motivates the heuristic approach but the practical relevance depends on the benchmark instances.
domain assumption The tested instances are representative of real LRS inputs, and CPLEX can solve them exactly enough to provide true optima.
The SOTA claim is only meaningful relative to this instance distribution; the abstract does not describe instance generation.
ad hoc to paper The random-key decoding procedure can represent all relevant LRS solutions, so the genetic search is not restricted to a suboptimal subspace.
The abstract says individuals are decoded from gray-value vectors; if this map is incomplete or biased, the best solution found may be bounded away from the optimum.

reviewed 2026-08-05 · how reviews work

0 comments

Cite this review

Pith. "Pith review of A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem." pith.science (2026). https://pith.science/paper/IWJPB2SK

@misc{pith2026250814020,
  author       = {Pith},
  title        = {Pith review of: A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IWJPB2SK}},
  note         = {Machine review of arXiv:2508.14020}
}

Share X Bluesky LinkedIn Reddit HN

read the original abstract

The longest run subsequence (LRS) problem is an NP-hard combinatorial optimization problem belonging to the class of subsequence problems from bioinformatics. In particular, the problem plays a role in genome reassembly. In this paper, we present a solution to the LRS problem using a Biased Random Key Genetic Algorithm (BRKGA). Our approach places particular focus on the computational efficiency of evaluating individuals, which involves converting vectors of gray values into valid solutions to the problem. For comparison purposes, a Max-Min Ant System is developed and implemented. This is in addition to the application of the integer linear programming solver CPLEX for solving all considered problem instances. The computation results show that the proposed BRKGA is currently a state-of-the-art technique for the LRS problem. Nevertheless, the results also show that there is room for improvement, especially in the context of input strings based on large alphabet sizes.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm
cs.NE 2025-09 conditional novelty 4.0

An LLM-generated, per-instance bias vector improves a BRKGA on the NP-hard Longest Run Subsequence problem, with statistically significant gains on 15 of 35 instance groups, concentrated on complex instances.

Reference graph

Works this paper leans on

14 extracted references · 12 canonical work pages · cited by 1 Pith paper

[1]

Approximation Algorithms for the Longest Run Subsequence Problem

Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka. Approximation Algorithms for the Longest Run Subsequence Problem . In Laurent Bulteau and Zsuzsanna Lipt\' a k, editors, Proceedings of CPM 2023 -- 34th Annual Symposium on Combinatorial Pattern Matching, volume 259 of Leibniz Internatio...

work page 2023
[2]

The hyper-cube framework for ant colony optimization

Christian Blum and Marco Dorigo. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 34 0 (2): 0 1161--1172, 2004

work page 2004
[3]

Metaheuristics for String Problems in Bio-informatics, volume 6

Christian Blum and Paola Festa. Metaheuristics for String Problems in Bio-informatics, volume 6. John Wiley & Sons, 2016

2016
[4]

STNWeb: a new visualization tool for analyzing optimization algorithms

Camilo Chacón Sartori , Christian Blum, and Gabriela Ochoa. STNWeb: a new visualization tool for analyzing optimization algorithms. Software Impacts, 17: 0 100558, 2023

work page 2023
[5]

Pattern recognition in bioinformatics

Dick de Ridder, Jeroen De Ridder, and Marcel JT Reinders. Pattern recognition in bioinformatics. Briefings in Bioinformatics, 14 0 (5): 0 633--647, 2013

work page 2013
[6]

The Longest Run Subsequence Problem: Further Complexity Results

Riccardo Dondi and Florian Sikora. The Longest Run Subsequence Problem: Further Complexity Results . In Pawe Gawrychowski and Tatiana Starikovskaya, editors, Proceedings of CPM 2021 -- 32nd Annual Symposium on Combinatorial Pattern Matching, volume 191 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1--14:15, Dagstuhl, Germany, 2021...

doi:10.4230/lipics.cpm.2021.14 2021
[7]

How do rna folding algorithms work? Nature Biotechnology, 22 0 (11): 0 1457--1458, 2004

Sean R Eddy. How do rna folding algorithms work? Nature Biotechnology, 22 0 (11): 0 1457--1458, 2004

work page 2004
[8]

Distributed and sequential algorithms for bioinformatics, volume 23

Kayhan Erciyes. Distributed and sequential algorithms for bioinformatics, volume 23. Springer, 2015

work page 2015
[9]

Biased random-key genetic algorithms for combinatorial optimization

Jos \'e Fernando Gon c alves and Mauricio GC Resende. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17 0 (5): 0 487--525, 2011

work page 2011
[10]

Hirschberg

Daniel S. Hirschberg. Algorithms for the longest common subsequence problem. Journal of the ACM, 24 0 (4): 0 664--675, 1977

work page 1977
[11]

A survey of sequence alignment algorithms for next-generation sequencing

Heng Li and Nils Homer. A survey of sequence alignment algorithms for next-generation sequencing. Briefings in Bioinformatics, 11 0 (5): 0 473--483, 2010

work page 2010
[12]

Adding negative learning to ant colony optimization: A comprehensive study

Teddy Nurcahyadi and Christian Blum. Adding negative learning to ant colony optimization: A comprehensive study. Mathematics, 9 0 (4): 0 361, 2021

work page 2021
[13]

Sven Schrinner, Manish Goel, Michael Wulfert, Philipp Spohr, Korbinian Schneeberger, and Gunnar W. Klau. The Longest Run Subsequence Problem . In Carl Kingsford and Nadia Pisanti, editors, Proceedings of WABI 2020 -- 20th International Workshop on Algorithms in Bioinformatics, volume 172 of Leibniz International Proceedings in Informatics (LIPIcs), pages ...

work page doi:10.4230/lipics.wabi.202 2020
[14]

Thomas St \"u tzle and Holger H. Hoos. MAX--MIN ant system. Future Generation Computer Systems, 16 0 (8): 0 889--914, 2000

work page 2000

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.

[1] [1]

Approximation Algorithms for the Longest Run Subsequence Problem

Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka. Approximation Algorithms for the Longest Run Subsequence Problem . In Laurent Bulteau and Zsuzsanna Lipt\' a k, editors, Proceedings of CPM 2023 -- 34th Annual Symposium on Combinatorial Pattern Matching, volume 259 of Leibniz Internatio...

work page 2023

[2] [2]

The hyper-cube framework for ant colony optimization

Christian Blum and Marco Dorigo. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 34 0 (2): 0 1161--1172, 2004

work page 2004

[3] [3]

Metaheuristics for String Problems in Bio-informatics, volume 6

Christian Blum and Paola Festa. Metaheuristics for String Problems in Bio-informatics, volume 6. John Wiley & Sons, 2016

2016

[4] [4]

STNWeb: a new visualization tool for analyzing optimization algorithms

Camilo Chacón Sartori , Christian Blum, and Gabriela Ochoa. STNWeb: a new visualization tool for analyzing optimization algorithms. Software Impacts, 17: 0 100558, 2023

work page 2023

[5] [5]

Pattern recognition in bioinformatics

Dick de Ridder, Jeroen De Ridder, and Marcel JT Reinders. Pattern recognition in bioinformatics. Briefings in Bioinformatics, 14 0 (5): 0 633--647, 2013

work page 2013

[6] [6]

The Longest Run Subsequence Problem: Further Complexity Results

Riccardo Dondi and Florian Sikora. The Longest Run Subsequence Problem: Further Complexity Results . In Pawe Gawrychowski and Tatiana Starikovskaya, editors, Proceedings of CPM 2021 -- 32nd Annual Symposium on Combinatorial Pattern Matching, volume 191 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1--14:15, Dagstuhl, Germany, 2021...

doi:10.4230/lipics.cpm.2021.14 2021

[7] [7]

How do rna folding algorithms work? Nature Biotechnology, 22 0 (11): 0 1457--1458, 2004

Sean R Eddy. How do rna folding algorithms work? Nature Biotechnology, 22 0 (11): 0 1457--1458, 2004

work page 2004

[8] [8]

Distributed and sequential algorithms for bioinformatics, volume 23

Kayhan Erciyes. Distributed and sequential algorithms for bioinformatics, volume 23. Springer, 2015

work page 2015

[9] [9]

Biased random-key genetic algorithms for combinatorial optimization

Jos \'e Fernando Gon c alves and Mauricio GC Resende. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17 0 (5): 0 487--525, 2011

work page 2011

[10] [10]

Hirschberg

Daniel S. Hirschberg. Algorithms for the longest common subsequence problem. Journal of the ACM, 24 0 (4): 0 664--675, 1977

work page 1977

[11] [11]

A survey of sequence alignment algorithms for next-generation sequencing

Heng Li and Nils Homer. A survey of sequence alignment algorithms for next-generation sequencing. Briefings in Bioinformatics, 11 0 (5): 0 473--483, 2010

work page 2010

[12] [12]

Adding negative learning to ant colony optimization: A comprehensive study

Teddy Nurcahyadi and Christian Blum. Adding negative learning to ant colony optimization: A comprehensive study. Mathematics, 9 0 (4): 0 361, 2021

work page 2021

[13] [13]

Sven Schrinner, Manish Goel, Michael Wulfert, Philipp Spohr, Korbinian Schneeberger, and Gunnar W. Klau. The Longest Run Subsequence Problem . In Carl Kingsford and Nadia Pisanti, editors, Proceedings of WABI 2020 -- 20th International Workshop on Algorithms in Bioinformatics, volume 172 of Leibniz International Proceedings in Informatics (LIPIcs), pages ...

work page doi:10.4230/lipics.wabi.202 2020

[14] [14]

Thomas St \"u tzle and Holger H. Hoos. MAX--MIN ant system. Future Generation Computer Systems, 16 0 (8): 0 889--914, 2000

work page 2000

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

The reading

Core claim §

What carries the argument

Load-bearing premise §

What would settle it §

If this is right

Where Pith is reading between the lines

discussion (0)

Core claim

Load-bearing premise

What would settle it