Pith. sign in

REVIEW 4 major objections 4 minor 19 references

BWT for string collections

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The Burrows-Wheeler transform of a string collection is not well-defined: different variants and input orders change the result, and the run count varies up to 31-fold on real biological data.

desk verdict A clear, useful survey of BWT variants for string collections that makes a real practical point — r should be standardized to r_opt — but its keystone structural lemma is borrowed from a companion paper and new dynamicity results lack proofs. read the letter →

arxiv 2506.01092 v1 pith:5WDDTSAP submitted 2025-06-01 cs.DS

Davide Cenzato , Zsuzsanna Lipták , Nadia Pisanti , Giovanna Rosone , Marinella Sciortino This is my paper
classification cs.DS
keywords Burrows-WheelertransformExtendedstringcollectionsnumberofrunscompressedtextindexescompressionbioinformatics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

At its core, this paper is a survey with a thesis: the standard ways of extending the Burrows-Wheeler transform (BWT) from a single string to a collection of strings are not interchangeable. It treats five named variants—EBWT, dollar-EBWT, multidollar-EBWT, multidollar-BWT, and concatenated-BWT (concatBWT)—as a family of distinct transforms and shows that on the same multiset they can produce different outputs even after ignoring separator names, with all differences confined to certain 'interesting intervals' defined by shared suffixes. Because several variants depend on the order in which the strings are given, the number of runs in the transform is not a property of the collection: on real biological data the paper reports the run count varying by a factor above 31 under input order alone. It therefore recommends standardizing the run count to $r_{opt}$, the minimum over all possible input orders of the multidollar variants, and shows that concatBWT—simple and widely used—cannot in general reach that minimum. The practical stakes are direct, because compressed BWT-based indexes store space proportional to the number of runs, so the choice of variant and string order controls index size.

What carries the argument

The central mechanism is the interesting interval: a range of the transform corresponding to a suffix shared by at least two input strings, whose left-context characters differ. Proposition 8 states that two separator-based BWT variants of the same multiset can differ only inside interesting intervals, and Lemma 7 states that distinct interesting intervals are disjoint; together these reduce all differences among variants to tie-breaking on shared suffixes. On top of this sits the paper's run-count machinery: the family $S_M$ of transforms obtained by running mdolEBWT or mdolBWT over every input order, with Theorem 17 guaranteeing that every separator-based variant appears in this family up to renaming the dollar symbols, and the tuple-ordering formulation of [27], solved as a shortest-path problem on a DAG in linear time and implemented by the optimalBWT tool [16,44], which computes $r_{opt}$ exactly. A secondary device is the input-order meta-string: the first $m$ characters of any separator-based transform form a permutation of the input strings, and for concatBWT that permutation is the BWT of this meta-string, which is why concatBWT cannot produce arbitrary output orders.

What would settle it

Enumerate all permutations of a small multiset of strings, compute every mdolEBWT and mdolBWT transform and every concatBWT transform, and compare run counts. The paper predicts that on some collections no concatBWT output can match the minimal run count $r_{opt}$; finding a multiset where a concatBWT output has fewer runs than every multidollar transform would contradict that conclusion, and in the same enumeration, checking whether any two separator-based variants differ at a position outside all interesting intervals would settle Proposition 8 directly.

Watch

Extended reading notes

Core claim

The paper establishes that the five separator-based BWT variants of a string collection are non-equivalent as transforms. For any two of them applied to the same multiset, the outputs can differ only inside interesting intervals—the ranges of the transform whose suffixes occur in at least two input strings—and distinct interesting intervals are disjoint, so each variant is determined by the tie-breaking rule it applies to shared suffixes. This localization has three consequences the paper develops: most variants are dynamic in the sense that deleting or adding a string only deletes or inserts characters in the transform, with concatBWT as the exception; the output order of concatBWT is essentially the BWT of the input-order meta-string, which makes it unable to realize many permutations; and run minimization can be studied over the family $S_M$ of all mdolEBWT and mdolBWT outputs over all string orders. Defining $r_{opt}$ as the minimum number of runs in this family, the paper reports experiments where the optimal order reduces runs by up to a factor of 31.49 compared with the input order on real read collections. It concludes that the parameter $r$ should be standardized to $r_{opt}$ rather than reported for an arbitrary variant and order.

Load-bearing premise

The comparison rests on the claim that two separator-based BWT variants of the same collection differ only inside blocks belonging to suffixes shared by at least two strings, and that these blocks never overlap; the proof is deferred to the supplementary material of an earlier paper, and if that characterization is incomplete, the analysis of where variants differ—and with it the dynamicity and output-order results—would break.

Editorial extensions

If this is right

  • If BWT run counts are to be compared across datasets or tools, they should be reported as $r_{opt}$, not as the run count of an arbitrary input order.
  • Compressed indexes whose space grows with the number of runs, such as the r-index, can be made substantially smaller on the same data by choosing a multidollar variant and an optimized string order; the reported gains on real reads reach 31.49 times.
  • Because concatBWT cannot produce all possible transforms, tools built on single-dollar concatenation are structurally unable to reach the minimum-run transform on some inputs.
  • The subsequence property of the non-concat variants means dynamic additions and removals of strings can in principle be supported by local edits to the transform rather than full recomputation.
  • Simple heuristics, notably colexicographic ordering and the plusBWT greedy rule, come close to $r_{opt}$ in experiments, giving a practical path to near-optimal indexes when full optimal ordering is too expensive.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • My inference: because the gain over input order is largest when many strings share long suffixes, datasets of short similar reads—RNA-seq, viral amplicons, ancient or clinical samples—are where order optimization pays most, and the same effect should appear in non-biological repetitive collections such as versioned files.
  • My inference: the fact that concatBWT's output order is the BWT of the input-order meta-string suggests that re-ordering input strings with a BWT-like pass could serve as a cheap pre-sorting heuristic for run reduction; the paper does not test this, but it follows directly from its Lemma 15.
  • My inference: $r_{opt}$ has a natural companion measure $n/r_{opt}$, the average run length under the optimal transform; normalizing datasets this way would make cross-dataset repetitiveness comparisons more meaningful than using the arbitrary input-order run count.
  • My inference: using the dynamicity results in practice requires care: deleting a string from mdolEBWT or mdolBWT preserves the subsequence property only if the relative order of the remaining strings is maintained, so dynamic index designs must keep ordering metadata explicit.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. This paper surveys five Burrows-Wheeler transform variants for string collections: EBWT, dolEBWT, mdolEBWT, mdolBWT, and concatBWT. It defines them precisely, compares them on a running example, classifies existing tools, and analyzes where the variants can differ via the notion of 'interesting intervals'. It further studies input-order dependence, dynamicity under addition/removal of strings, and output-order transformations (the 'meta-string' view). The paper then argues that the number of BWT runs r is not well-defined for a collection and proposes standardizing it to r_opt, the minimum number of runs over all mdolEBWT/mdolBWT string orders; it presents the optimalBWT algorithm and heuristics, reports experimental run-count reductions on real biological data, and closes with a survey of bioinformatics applications.

Significance. If the claims are correct, the paper is a useful systematization of an area where terminology and tool outputs have been inconsistent: it gives a clean taxonomy, a precise language for discussing where variants differ, and a concrete proposal (r_opt) for benchmarking repetitive string collections. The paper is honest about provenance: experimental numbers in Table 7 are attributed to [32], and the proof of Proposition 8 is explicitly deferred to the supplementary material of [47]. The running examples and the tool classification in Table 1 are valuable contributions. However, the central recommendation is currently overstated, and several load-bearing statements are either false as written or lack proofs in this manuscript, so the contribution is not yet in a form where the r_opt standardization claim can be accepted without qualification.

major comments (4)
  1. [Section 5, Definition 18 (with Abstract and Section 1)] The abstract and Section 1 say that r should be standardized to r_opt, 'the minimum number of runs among all possible transforms', but Definition 18 defines r_opt as the minimum over S_M, the family of mdolEBWT/mdolBWT transforms only. This is not the minimum over all BWT variants introduced in Section 3. For example, for M={banana,banana}, EBWT(M) is 'nnnnbbaaaaaa' and has 3 runs, while the unique mdolEBWT transform (with the two dollar occurrences identified for run counting, as in Section 5) is 'aannnnbb$$aaaa' and has 5 runs. Thus r_opt(S_M) is larger than the run count of a valid BWT variant of the same collection. The standardization recommendation must either be explicitly restricted to separator-based transforms throughout, or Definition 18 must be broadened; as written, the central claim is overstated.
  2. [Section 4.4, Theorem 17 (with Eq. (5))] Theorem 17 claims that every separator-based BWT variant can be simulated by mdolEBWT and mdolBWT up to renaming dollars. This is false for concatBWT as defined in Eq. (5), because concatBWT has an extra leading '$' and a final '#', making its length one larger than any mdolBWT output. For M=(GTC,GT), concatBWT(M) is '$TCT$#GG' (length 8), while every mdolBWT output for this collection has length 7; renaming dollars cannot change the length. The theorem holds only for the adapted concatBWT, or for equality up to deleting the leading '$' and renaming '#' as '$'. This qualification must be added in Section 4.4 and carried through the uses of Theorem 17 in Section 5.
  3. [Section 4.2, Proposition 8] Proposition 8 is the structural keystone of the paper: it is used to justify that all differences between separator-based variants are confined to disjoint interesting intervals, to support Theorem 17, and to motivate Definition 18 and the optimality of the algorithms discussed in Section 5. Its proof is not included here; the text says only 'For the proof, see the Supplemental Material of [47]'. Since this manuscript presents the classification and the r_opt proposal as a self-contained contribution, the reader cannot verify the central claim from this paper alone. Please include a proof, or at least a complete proof sketch, in this paper, or explicitly state that Section 5 is conditional on a result proved only in [47].
  4. [Section 4.3, Propositions 11 and 12] Propositions 11 and 12 are described as new (Section 1.1 says Section 4.3 is newly added), but no proofs are given. The subsequence claims are not immediate because ties in omega-order and lexicographic order among identical rotations or suffixes are broken by string indices, and those indices change when a subcollection is removed. A proof or a detailed proof sketch is needed before the conclusion that 'all the considered BWT-variants can be used as basis of dynamic compressed indexing structures' can be accepted. In particular, Proposition 12's 'up to renaming the dollar symbols' needs a precise statement of how the renaming interacts with the relative order of the remaining strings.
minor comments (4)
  1. [Throughout] There are several typos and misspellings: 'bionformatics' appears in the Introduction and in Section 6, 'practicioners' appears in the Introduction, and Section 3.2 contains 'we have r an additional dollar', which should be 'we have an additional dollar'.
  2. [Table 7] The rightmost column header 'r input/ropt' would be clearer as 'r_input/r_opt', and the caption should state explicitly that the run counts treat all dollar symbols as equal, as noted in Table 5.
  3. [Section 3.2] The definition of the adapted concatBWT is introduced informally ('we denote by adapted concatBWT, the transform obtained by removing the first symbol from concatBWT and replacing the # by $'). Since the adapted variant is used later in Sections 4.4 and 5, it should be given a formal definition or equation number.
  4. [Section 4.4] The notation for the output-permutation transforms pi_dolE, pi_mdolE, pi_mdol, and pi_concat is introduced in the text but not summarized in a table or displayed list; a small table or displayed enumeration would improve readability.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: variants and run-count comparisons rest on explicit examples and measured experiments, though key structural facts are cited to the authors' own prior work.

full rationale

I walked the derivation chain from the five BWT variants (Section 3) through the combinatorial analysis (Section 4) to the run-minimization claims (Section 5). The differences between variants are established by explicit constructions and worked examples (Tables 2-3, Examples 1-5), not by assuming the conclusion. Proposition 8, the structural claim that two separator-based BWTs differ only in interesting intervals, is the keystone for Theorem 17 and for the definition of r_opt over S_M; its proof is deferred to the Supplementary Material of [47], a paper by two of the current authors. This is a conspicuous self-citation and an omitted proof in this manuscript, and if the proposition were incomplete the reduction of 'all separator-based transforms' to S_M would be unsupported. However, it is not a circular step in the sense of this review: [47] is a separate published work with a proof, and the present paper does not redefine 'interesting interval' in terms of r_opt or fit parameters into the conclusion. The dynamicity results (Propositions 11-12) follow from order preservation of rotations and suffixes (Lemma 10), and the 31x run-count reduction is an experimental measurement reported from [32,44], not a fitted quantity renamed as a prediction. No equation in the paper is equivalent to its input by construction. I therefore find no significant circularity; the score of 2 reflects minor but disclosed reliance on the authors' own prior publications, which does not by itself make the derivation circular.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no ad hoc free parameters or invented entities. It relies on several unproved results from prior work, chiefly Proposition 8 and Lemma 6 from the authors' earlier papers, which are central to the comparative analysis; proofs are deferred to supplementary material. The empirical run-count table is taken from [32].

assumptions (3)
  • domain assumption Proposition 8 (from [47]): two separator-based BWT variants of the same multiset differ only within interesting intervals, and interesting intervals are disjoint.
    Used throughout Sections 4.2-4.4 to localize differences; proof not included, deferred to Supplementary Material of [47].
  • domain assumption Lemma 6 (from [47]): mdolBWT(M) and mdolEBWT(M) produce the same string up to renaming dollars, and dolEBWT corresponds to mdolBWT on lexicographically sorted input.
    Basis for grouping tools and for defining the family S_M in Section 5; proof deferred to [47].
  • standard math The Extended BWT (Mantaci et al. 2007) is reversible and has the clustering property, with recovery via the Gessel-Reutenauer bijection.
    Used in Section 3.1 to reconstruct the strings from the EBWT and to claim the clustering effect.

how reviews work

0 comments
Cite this review

Pith. "Pith review of BWT for string collections." pith.science (2026). https://pith.science/paper/5WDDTSAP

@misc{pith2026250601092,
  author       = {Pith},
  title        = {Pith review of: BWT for string collections},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5WDDTSAP}},
  note         = {Machine review of arXiv:2506.01092}
}
read the original abstract

We survey the different methods used for extending the BWT to collections of strings, following largely [Cenzato and Lipt\'ak, CPM 2022, Bioinformatics 2024]. We analyze the specific aspects and combinatorial properties of the resulting BWT variants and give a categorization of publicly available tools for computing the BWT of string collections. We show how the specific method used impacts on the resulting transform, including the number of runs, and on the dynamicity of the transform with respect to adding or removing strings from the collection. We then focus on the number of runs of these BWT variants and present the optimal BWT introduced in [Cenzato et al., DCC 2023], which implements an algorithm originally proposed by [Bentley et al., ESA 2020] to minimize the number of BWT-runs. We also discuss several recent heuristics and study their impact on the compression of biological sequences. We conclude with an overview of the applications and the impact of the BWT of string collections in bioinformatics.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 10 canonical work pages

  1. [1]

    2BEETL.https://github.com/BEETL/BEETL

    1BCR_LCP_GSA.https://github.com/giovannarosone/BCR_LCP_GSA. 2BEETL.https://github.com/BEETL/BEETL. 3BigBWT.https://github.com/alshai/Big-BWT. 4bwt-lcp-parallel.https://github.com/AlgoLab/bwt-lcp-parallel. 5bwt-lcp-parallel.https://github.com/AlgoLab/bwt-lcp-em/. 6cais.https://github.com/davidecenzato/cais. 7CMS-BWT. https://github.com/fmasillo/CMS-BWT. 8e...

    2020

  2. [4]

    42 Vincenzo Carletti, Pasquale Foggia, Erik Garrison, Luca Greco, Pierluigi Ritrovato, and Mario Vento

    doi:10.1093/bioinformatics/ btz782. 42 Vincenzo Carletti, Pasquale Foggia, Erik Garrison, Luca Greco, Pierluigi Ritrovato, and Mario Vento. Graph-based representations for supporting genome data analysis and visualization: Opportunities and challenges. In12th IAPR-TC-15 International Work- shop Graph-Based Representations in Pattern Recognition (GbRPR), p...

    doi:10.1093/bioinformatics/

  3. [14]

    73 Dan Gusfield.Algorithms on Strings, Trees, and Sequences - Computer Science and Computa- tional Biology

    Springer Nature Switzerland.doi:10.1007/978-3-031-38854-5\_6. 73 Dan Gusfield.Algorithms on Strings, Trees, and Sequences - Computer Science and Computa- tional Biology. Cambridge University Press, 1997.doi:10.1017/CBO9780511574931. 74 James Holt and Leonard McMillan. Merging of multi-string bwts with applications.Bioinform., 30(24):3524–3531, 2014.doi:10...

    work page doi:10.1007/978-3-031-38854-5 1997

  4. [15]

    76 Alan Kuhnle, Taher Mun, Christina Boucher, Travis Gagie, Ben Langmead, and Giovanni Manzini

    doi:10.1093/BIOINFORMATICS/ BTT257. 76 Alan Kuhnle, Taher Mun, Christina Boucher, Travis Gagie, Ben Langmead, and Giovanni Manzini. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment.J. Comput. Biol., 27(4):500–513, 2020.doi:10.1089/CMB.2019.0309. 77 Ben Langmead and Steven L Salzberg. Fast gapped-read alignment with Bowtie 2.Natur...

    arXiv

  5. [17]

    87 Bo Liu, Dixian Zhu, and Yadong Wang. deBWT: parallel construction of Burrows-Wheeler Transform for large collection of genomes with de Bruijn-branch encoding.Bioinform., 32(12):174–182, 2016.doi:10.1093/BIOINFORMATICS/BTW266. 28 BWT for string collections 88 Felipe A. Louza, Guilherme P. Telles, Simon Gog, Nicola Prezza, and Giovanna Rosone. gsufsort: ...

    work page doi:10.1093/bioinformatics/btw266 2016

  6. [20]

    110 Pramesh Shakya, Ardalan Naseri, Degui Zhi, and Shaojie Zhang

    URL: https://www.biorxiv.org/content/ early/2025/02/07/2025.02.03.634410,doi:10.1101/2025.02.03.634410. 110 Pramesh Shakya, Ardalan Naseri, Degui Zhi, and Shaojie Zhang. mcPBWT: Space-Efficient Multi-column PBWT Scanning Algorithm for Composite Haplotype Matching. In11th International Conference on Computational Advances in Bio and Medical Sciences (ICCAB...

    work page doi:10.1101/2025.02.03.634410 2025

  7. [1993]

    doi:10.1016/0097-3165(93) 90095-P. D. Cenzato et al. 27 68 Raffaele Giancarlo, Antonio Restivo, and Marinella Sciortino. From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization.Theor. Comput. Sci., 387:236 – 248, 2007.doi:10.1016/J.TCS.2007.07.019. 69 Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola P...

    work page doi:10.1016/0097-3165(93

  8. [2005]

    An extension of the Burrows-Wheeler Transform.Theor

    91 Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino. An extension of the Burrows-Wheeler Transform.Theor. Comput. Sci., 387(3):298–312, 2007.doi:10.1016/J. TCS.2007.07.014. 92 Sabrina Mantaci, Antonio Restivo, and Marinella Sciortino. Burrows-Wheeler transform and Sturmian words.Inf. Process. Lett., 86(5):241–246, 2003.doi:10.101...

    arXiv 2007

Show all 19 references
  1. [2009]

    79 Ben Langmead, Cole Trapnell, Mihai Pop, and Steven L Salzberg

    doi:10.1186/ gb-2009-10-11-r134. 79 Ben Langmead, Cole Trapnell, Mihai Pop, and Steven L Salzberg. Ultrafast and memory- efficient alignment of short DNA sequences to the human genome.Genome Biology, 10:R25, 2009.doi:10.1186/gb-2009-10-3-r25. 80 Brice Letcher, Martin Hunt, and...

    2009 doi

  2. [2013]

    Generic non-recursive suffix array construction.ACM Trans

    101 Jannik Olbrich, Enno Ohlebusch, and Thomas Büchler. Generic non-recursive suffix array construction.ACM Trans. Algorithms, 20(2), 2024.doi:10.1145/3641854. 102 Marco Oliva, Travis Gagie, and Christina Boucher. Recursive prefix-free parsing for building big BWTs. In33rd Dat...

    2024

  3. [2014]

    58 Lavinia Egidi, Felipe A

    doi:10.1093/BIOINFORMATICS/ BTU014. 58 Lavinia Egidi, Felipe A. Louza, Giovanni Manzini, and Guilherme P. Telles. External memory BWT and LCP computation for sequence collections with applications.Algorithms Mol. Biol., 14(1):6:1–6:15, 2019.doi:10.1186/S13015-019-0140-0. 59 Pa...

  4. [2015]

    57 RichardDurbin

    doi:10.1371/journal.pbio.1002195. 57 RichardDurbin. EfficienthaplotypematchingandstorageusingthepositionalBurrows-Wheeler transform (PBWT).Bioinform., 30(9):1266–1272,

    doi

  5. [2016]

    54 Diego Díaz-Domínguez and Gonzalo Navarro

    doi:10.1101/gr.210641.116. 54 Diego Díaz-Domínguez and Gonzalo Navarro. Efficient construction of the extended BWT from grammar-compressed DNA sequencing reads.CoRR, abs/2102.03961,

    arXiv

  6. [2019]

    40 Michael Burrows and David J

    doi:10.1186/S13015-019-0148-5. 40 Michael Burrows and David J. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation,

    doi

  7. [2021]

    48550/arXiv.2102.03961

    doi:10. 48550/arXiv.2102.03961. 55 Diego Díaz-Domínguez and Gonzalo Navarro. Efficient construction of the BWT for repetitive text using string compression.Inf. Comput., 294:105088,

    doi arXiv

  8. [2022]

    25 Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piatkowski

    doi:10.1007/ s11047-022-09882-6. 25 Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piatkowski. Constructing and indexing the bijective and extended Burrows-Wheeler transform.Inf. Comput., 297:105153, 2024.doi:10.1016/J.IC.2024.105153. 26 Markus J. Bauer, Anthony J. C...

    2024

  9. [2023]

    doi:10.1016/j.ic.2023. 105088. 56 Zachary D.Stephens, Skylar Y.Lee, Faraz Faghri, Roy H.Campbell, Chengxiang Zhai, and Miles J.Efron et al. Big data: Astronomical or genomical?PLoS Biol, 13(7):e1002195,

    2023 doi

  10. [2024]

    SOPanG: online text searching over a pan-genome.Bioinform., 34(24):4290–4292, 2018.doi:10.1093/BIOINFORMATICS/BTY506

    50 Aleksander Cislak, Szymon Grabowski, and Jan Holub. SOPanG: online text searching over a pan-genome.Bioinform., 34(24):4290–4292, 2018.doi:10.1093/BIOINFORMATICS/BTY506. 51 The COVID-19 Genomics UK (COG-UK) consortium. An integrated national scale SARS- CoV-2 genomic survei...

    2018 doi

  11. [2025]

    46 Davide Cenzato and Zsuzsanna Lipták

    Submitted. 46 Davide Cenzato and Zsuzsanna Lipták. A theoretical and experimental analysis of BWT variants for string collections. In33rd Annual Symposium on Combinatorial Pattern Matching (CPM), volume 223 ofLIPIcs, pages 25:1–25:18, 2022.doi:10.4230/LIPICS.CPM.2022.25. 47 Da...

    2022 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.