REVIEW 3 major objections 4 minor
Patching leaky tunnels in BWTs
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Run-length compressed patterns can be matched against compressed texts in time proportional to their number of runs rather than their length.
desk verdict Nice idea for run-length compressed MEM-finding, but the main theorem currently rests on a deferred proof of the central subroutine. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument rests on three components. RL hashing is a Karp-Rabin variant defined on the run-length encoding of a string, letting any substring delimited by two run-internal offsets be hashed in constant time after $O(\rho_P)$ preprocessing. A suffixient set is a small set of text positions covering all suffix-tree branching edges; a modified z-fast trie stores the reversed prefixes of $T$ ending at those positions and answers longest-common-suffix queries in $O(\log m)$ time. Run-boundary pointers in $T$ resolve mismatches at the start of runs in constant time by jumping to an earlier position whose prefix shares the longest common suffix.
What would settle it
Build the Lemma 3 data structure for a text with a known suffixient set and query it with all prefixes of a run-compressed pattern, counting trie nodes and hash operations per query. Any prefix that requires more than $O(\log m)$ such operations, or any data structure exceeding $O(\chi)$ space after $O(\rho_P)$ preprocessing, would falsify the theorem. A concrete stress test is a de Bruijn-like highly repetitive text with small $\chi$ and patterns with many short runs.
Extended reading notes
Core claim
The central claim is Theorem 4: store $T$ in $O(\rho_T+\chi)$ space and, given $P$ with $\rho_P$ runs, find all MEMs in $O(\rho_P\log m)$ time plus constant time for every suffix-tree edge fully or partially descended. The proof route replaces Karp-Rabin hashing by a run-length hash: after $O(\rho_P)$ preprocessing, any substring of $P$ between two positions inside runs can be hashed in constant time. Mismatches at run starts in $T$ are handled by pointers from each run start to an earlier position with the longest common suffix, and mismatches at run starts in $P$ are handled by a modified z-fast trie over reversed prefixes of $T$ ending at suffixient positions, answering longest-common-suf
Load-bearing premise
Lemma 3 asserts that a modified z-fast trie over reversed prefixes of $T$ ending at suffixient positions can answer the longest-common-suffix query for any prefix of $P$ in $O(\log m)$ time after $O(\rho_P)$ preprocessing while using $O(\chi)$ space, and the paper defers the proof to the full version; if that subroutine fails, the $O(\rho_P\log m)$ query time does not follow.
Editorial extensions
If this is right
- MEM queries on repetitive texts no longer require $O(m)$ or $O(m\log\sigma/\log n)$ preprocessing per pattern; the cost is $O(\rho_P\log m)$ plus one constant-time step per suffix-tree edge visited.
- The space bound $O(\rho_T+\chi)$ can be much smaller than $n$; since $\chi\le 2r$ and $\chi\le 2\bar r$, it stays comparable to RLBWT-based indexes.
- SMEM queries against sparse haplotype panels run in time proportional to the number of panel edges descended plus $\sum_{Q[j]=1}(1+\log \sum_k M[k][j])$, with space proportional to the number of 1s in the panel.
- The RL hash is a reusable primitive: it gives constant-time equality hashing for substrings of run-length compressed patterns without a near-linear preprocessing pass.
Reading between the lines
- If the deferred proofs of Lemma 3 and the right-to-left pass hold as stated, the same run-boundary idea could be applied to variation graphs: long runs of 0/1 edges in a haplotype walk might be crossed in constant time using succinct representations of permutations and functions, rather than edge by edge.
- The two-pass matching-statistics structure suggests the technique generalizes beyond MEMs to other statistics usually computed via suffix-tree walks, such as matching statistics or longest-common-prefix arrays for run-compressed inputs.
- For bi-allelic panels with rare variants, the SMEM index should be tested against PBWT implementations on real genotype data; if query time indeed only charges columns with 1s, sparse queries will be nearly independent of panel width.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an index for finding maximal exact matches (MEMs) when both text T and pattern P are given in run-length compressed form. The main result (Theorem 4) claims O(rho_T + chi) space and O(rho_P log m) query time, plus a constant per suffix-tree edge descended, where rho_T and rho_P are the numbers of runs and chi is the size of a smallest suffixient set. The approach modifies Depuydt et al.'s suffixient-set index by introducing 'RL hashes' for run-length compressed strings and by using a modified z-fast trie over reversed prefixes at suffixient positions to answer longest-common-suffix queries. A further adaptation (Theorem 5) is claimed for set-maximal exact matches (SMEMs) in sparse haplotype panels, with space proportional to the number of 1s in the panel. The paper is clearly written and the motivation is sound, but several load-bearing proofs are deferred to a non-existent full version.
Significance. If the main theorem is correct, it is a meaningful contribution: it removes the O(m log sigma / log n) preprocessing cost of Depuydt et al.'s MEM index when the pattern is run-length compressed, which is relevant for pangenomic and haplotype applications where query patterns are sparse or highly repetitive. The SMEM adaptation targets an important bioinformatics problem. However, the significance is currently conditional: the central query-time bound rests on Lemma 3, whose proof is explicitly deferred, and on a right-to-left pass whose details are also deferred. The paper does not contain an implementation or experimental validation, which is not required for a theory paper, but it also does not contain complete proofs of its main claims.
major comments (3)
- [Section 2, Lemma 3] Lemma 3 is the key subroutine that supplies the longest-common-suffix query used at run boundaries of P. Its proof is explicitly left to the full version ('whose proof we leave to the full version of this paper because z-fast tries are somewhat complicated'). Since Theorem 4 and the correctness of the left-to-right pass in Section 3 both depend on this lemma, the main query bound O(rho_P log m) is not substantiated by the submitted manuscript. The authors should provide a complete proof or a precise pointer to a verifiable published version; a statement of the lemma alone is not sufficient for the central claim.
- [Section 3, right-to-left pass] The right-to-left pass is needed to turn the left-to-right matching-statistics information into the actual MEMs. The text says: 'With some attention to details that we will cover more thoroughly in the full version of this paper, this gives us the following theorem.' The details of this pass are load-bearing: they determine both correctness and the claimed O(rho_P log m) time (or O(rho_P) plus per-edge cost). As written, the proof of Theorem 4 is incomplete at this step.
- [Section 4, Theorem 5] Theorem 5 is presented as the main application, but the entire adjustment of the Section 3 machinery to per-column tries and pointers is deferred: 'Adjusting the details of Section 3 appropriately gives us the following theorem. We defer the details of that adjustment to the full version of this paper.' The claimed space bound 'proportional to the number of 1s in M' and the query time bound therefore lack proof. This is especially problematic because the sparse-haplotype setting changes the data structures (per-column centroid decompositions, pointers for 1s) and the query semantics (SMEMs rather than MEMs), so the reduction is not automatic.
minor comments (4)
- [Section 2, Lemma 2] The proof of Lemma 2 also leaves the detailed constant-time hash combination to the full version ('which we will describe in detail in the full version of this paper'). The sketch is plausible, but since the result is used by Lemma 3, including the explicit formulas for combining the three RL-hash pieces would improve self-containedness.
- [Section 1] The sentence defining suffixient sets has a typo: 'it in some sense it is sufficient' should be 'it is in some sense sufficient'.
- [Section 3] The term 'edge we would fully or partially descend in the suffix tree for T' is used in Theorem 4 but not formally defined. In particular, it is unclear whether partially descended edges are counted per character or per suffix-tree edge, and whether this count is bounded independently of m.
- [References] Reference [13] is cited as 'Personal communication, 2026.' This is not verifiable by the reader; if the jump index is described in an unpublished manuscript or technical report, that should be cited instead, or the relevant properties should be stated explicitly.
Circularity Check
No significant circularity; the main claims rest on deferred technical proofs, not on reduction to inputs or self-citation chains.
full rationale
The paper extends Depuydt et al.'s suffixient-set MEM index (with one overlapping author) by introducing run-length hashes and modified z-fast tries. The new query bound in Theorem 4 depends on Lemma 3, whose proof is explicitly deferred to the full version, and on right-to-left pass details that are also deferred. These are completeness gaps, not circular reasoning: nowhere does the paper define the conclusion in terms of its inputs, fit parameters to the target MEMs, or import a uniqueness result from the authors' prior work as the sole justification for a forced choice. The citations to the authors' own papers are background constructions or inspiration (including Groot Koerkamp's personal-communication 'jump index'), and none of them is used as the only evidence for the central claim. No equation or construction is shown to be equivalent by definition to another part's output. Thus the derivation chain is not circular, although it is incomplete.
Assumptions & free parameters
assumptions (5)
- standard math Word-RAM model with constant-time word operations and O(w)-bit machine words; each run's encoding fits in O(w) bits.
- standard math Karp-Rabin hashing modulo a random prime has negligible collision probability; substring hashes can be combined arithmetically.
- domain assumption A smallest suffixient set X for T exists, has size chi, and can be stored; it covers all suffix-tree branch labels.
- ad hoc to paper Lemma 3: the modified z-fast trie over reversed prefixes at suffixient positions answers the required LCS query in O(log m) after O(rho_P) preprocessing in O(chi) space.
- domain assumption Durbin's pair encoding of haplotypes (each cell as (j, M[i][j])) makes MEMs in the multi-string BWT correspond to SMEMs of the haplotype query.
Cite this review
Pith. "Pith review of Patching leaky tunnels in BWTs." pith.science (2026). https://pith.science/paper/AQRDZ5SP
@misc{pith2026260801387,
author = {Pith},
title = {Pith review of: Patching leaky tunnels in BWTs},
year = {2026},
howpublished = {\url{https://pith.science/paper/AQRDZ5SP}},
note = {Machine review of arXiv:2608.01387}
}
read the original abstract
We extend Baier's foundationial work on tunnelling Burrows-Wheeler Transforms (BWTs) by showing how something that would be a good tunnel except for a strings that diverge from the tunnel (``leaks'') can be patched and turned into a tunnel. Whereas augmenting a BWT with a normal tunnel takes extra space proportional to the tunnels length, augmenting it with a patched tunnels take that plus space proportional to the number of leaks.
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.