REVIEW 3 major objections 4 minor 14 references
Matching reads to many genomes with the $r$-index
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The r-index can be built and queried for large repetitive genome collections, making compressed exact matching to many genomes practical.
desk verdict A clear, honest user guide for the r-index software; the only real weakness is a single unrepeatable benchmark, which is easy to fix or qualify. 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 central object is the r-index, a run-compressed FM-index whose space is O(r) machine words, where r is the number of runs in the Burrows-Wheeler Transform of the database. Rather than storing the full transform, it stores one sampled entry per run, and that is enough to support backward search for counting and to locate pattern occurrences. Construction in the walkthrough uses bigbwt, an algorithm designed for large repetitive collections, with the sais suffix-array algorithm available as a fallback for small or insufficiently repetitive inputs; a companion file stores the mapping from text offsets to sequence names, which is what lets locate output named SAM records instead of bare positions.
What would settle it
Run ri-buildfasta on a 110 GB collection of 2000 genomes chosen to be non-repetitive, such as diverse bacterial species, using the same server and one thread. If the resulting .ri files approach the size of the uncompressed input, or if construction memory scales with total text length rather than with run count, then the demonstrated compression and speed reflect the repetitiveness of the test data and not a general property of the r-index.
Extended reading notes
Core claim
The r-index can be used in practice: with the bundled programs, a complete compressed index of a large repetitive genome collection can be built and queried for exact matches. For 2000 copies of human chromosome 19 from different individuals, 110 GB of uncompressed sequence becomes a 665 MB index, built in under 5 hours on a server using 41 GB of RAM and a single thread. Once built, ri-align count reports for each read the longest suffix that occurs in the collection and how many times it occurs, and ri-align locate reports the positions of exact matches in SAM format, with reference sequence names resolved from the offset-to-name mapping. The implementation is released as open source, so the walkthrough serves as both documentation and a reproducibility record.
Load-bearing premise
The practical space and time figures all depend on the Burrows-Wheeler Transform having few runs: the database must be repetitive enough that the number of runs r stays far below the text length, and the paper itself notes that for small or insufficiently repetitive collections the alternative construction may be faster.
Editorial extensions
If this is right
- If the reported results hold, a 110 GB collection of 2000 human chromosomes can be queried through a 665 MB index, so pangenome-scale exact matching becomes possible on ordinary servers with far less disk and memory than the raw sequences require.
- For reads with errors or novel variation, the count command's longest-suffix length and occurrence count can be used directly as seeds: users can truncate reads to the longest suffix that occurs, then locate those suffixes.
- Because the original FASTA file is not needed after the index is built, storing and sharing a database reduces to storing the .ri files plus the small name-mapping file.
- Since locate reports all occurrences unless --max-hits is set, users can control run time on highly repetitive reads by capping the number of reported hits or restricting to reads with at most k occurrences using --max-range.
Reading between the lines
- The paper leaves implicit that this changes storage economics: after one construction, queries do not touch the raw sequences, so repeated searches amortize the build cost, and the index files become small enough to distribute alongside the reads.
- A natural extension the authors do not develop is using the longest-suffix counts as a simple mapping-quality proxy: a read with a long, unique suffix is more confidently placed than one whose longest match appears hundreds of times, and the count command already produces the raw numbers needed.
- The reported single-threaded construction suggests a direct scalability test: repeated runs on random subsets of the 2000-chromosome collection would show whether build time and index size grow with collection size at the rate expected for a repetitive corpus, separating the algorithm's scaling from the machine's speed.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper is a brief practical guide to ri-buildfasta and ri-align, two programs implementing the r-index for compressed indexing of genomic databases. It gives step-by-step installation instructions, example commands for building an r-index from a FASTA file and for counting or locating occurrences of reads from a FASTQ file, and explains how to interpret the tabular count output and the SAM-format locate output. It also reports small illustrative timings on a dengue virus dataset and a larger benchmark on a collection of 2000 human chromosome 19 copies. The underlying data structures and algorithms are taken from the authors' earlier papers, so the paper's contribution is as a software tutorial rather than a new algorithmic result.
Significance. If the software works as described, this guide is useful to researchers who want to index large repetitive genome collections in modest memory. The paper's strengths are its brevity, the inclusion of exact shell commands, the sample input files bundled with the repository, and the sample outputs that let users verify their installation. The source code is released under GPLv3, which supports reproducibility. However, the paper's only quantitative evidence for scalability is a single self-reported construction of an index for 2000 human chromosome 19 copies, and that report lacks the version, dataset, and correctness details needed for independent verification. The guide's practical value therefore rests on an unverified benchmark claim.
major comments (3)
- [§3 (Construction)] The central scalability claim is the sentence in Section 3: "With bigbwt we have built a 665 MB r-index for a collection of 2000 copies of human chromosome 19 from different individuals, which take 110 GB uncompressed, in under 5 hours on a server using 41 GB of RAM and one thread." This claim is load-bearing for the guide's message that the r-index is practical for large pan-genomic collections, but the manuscript does not report the exact software version or commit, the full construction command and parameter choices, the source or accession identifiers of the 2000 chromosome copies, or any correctness check of the resulting index. Please add these details or explicitly label the run as anecdotal and remove it as evidence of practical scalability.
- [§3 (Construction)] The dengue benchmark in Section 3, reporting that building the index takes "about 3 seconds and 47 MB of memory" with bigbwt and "about 10 seconds and 104 MB of memory" with sais, gives no measurement methodology: it does not say whether the values are single runs or averages, how memory was measured, or what portion of the collection was indexed. Please state the measurement procedure or qualify these numbers as rough single-machine illustrations.
- [§3 (Construction)] The statement that bigbwt "efficiently handles most large repetitive text collections" is not quantified, so the boundary of the claimed applicability is undefined. Please provide a practical characterization of the regime in which bigbwt is expected to be faster or more space-efficient than sais, for example in terms of the BWT run count r relative to the text length n, or soften the claim to avoid overgeneralization.
minor comments (4)
- [§3 (Construction)] The phrase "which take 110 GB uncompressed" should be "which occupy 110 GB uncompressed" or similar, since files do not "take" memory in this context.
- [§5 (Interpreting Counts)] The text says "to create simlulated.0.3edits" but the sample output shows "simulated.0.3edits"; the extra "l" appears to be a typo.
- [§6 (Interpreting Locations)] In the description of the SAM fields, "the position of the occurrence of the read is in that sequence" should be rephrased to "the position of the occurrence in that sequence" for clarity.
- [§4 (Alignment)] The sentence "The output is piped to the standard output by default" should be "written to standard output by default," since no pipe is involved.
Circularity Check
No significant circularity: the paper is a software guide that makes no derivation-based predictions; its performance numbers are empirical reports, not consequences of fitted inputs.
full rationale
This manuscript is an application/tutorial note describing how to build and query an r-index with ri-buildfasta and ri-align. It contains no derivation chain in which a quantity is defined in terms of another and then predicted from it. The central statements are operational: commands for installation, construction, counting, and locating, plus measured timings and memory usage for two datasets (Dengue and human chromosome 19). The only load-bearing claims about scalability are empirical reports ('with bigbwt we have built a 665 MB r-index... in under 5 hours on a server using 41 GB of RAM and one thread'), not mathematically derived predictions; they could be false or hard to reproduce without being circular. References to prior work by the same authors (Boucher et al. 2019, Kuhnle et al. 2019, and Gagie/Navarro/Prezza 2018) are background citations for algorithms that the guide uses; the paper does not invoke them to rule out alternatives or to justify a choice as forced. The acknowledged limitations (no mapping-quality or paired-end support; bigbwt only efficient for large repetitive collections) are caveats, not hidden circular inputs. No fitted parameter is renamed as a prediction, no ansatz is smuggled in via citation, and no known result is merely renamed. Therefore the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (2)
- standard math The correctness and efficiency of the BWT, FM-index, and r-index data structures as described in Gagie, Navarro and Prezza [4], Boucher et al. [1], and Kuhnle et al. [6].
- domain assumption The input genome collections are sufficiently repetitive that the number of BWT runs, r, is small enough to make the O(r)-space index practical.
Cite this review
Pith. "Pith review of Matching reads to many genomes with the $r$-index." pith.science (2026). https://pith.science/paper/M5M4VK5I
@misc{pith2026190801263,
author = {Pith},
title = {Pith review of: Matching reads to many genomes with the $r$-index},
year = {2026},
howpublished = {\url{https://pith.science/paper/M5M4VK5I}},
note = {Machine review of arXiv:1908.01263}
}
abstract
The $r$-index is a tool for compressed indexing of genomic databases for exact pattern matching, which can be used to completely align reads that perfectly match some part of a genome in the database or to find seeds for reads that do not. This paper shows how to download and install the programs ri-buildfasta and ri-align; how to call ri-buildfasta on a FASTA file to build an $r$-index for that file; and how to query that index with ri-align. Availability: The source code for these programs is released under GPLv3 and available at https://github.com/alshai/r-index .
Reference graph
Works this paper leans on
-
[1]
Prefix-free parsing for building big BWTs
Christina Boucher, Travis Gagie, Alan Kuhnle, Ben Langm ead, Giovanni Manzini, and Taher Mun. Prefix-free parsing for building big BWTs. Algorithms for Molecular Biology , 14(1):13, 2019
work page 2019
-
[2]
A block-sorting los sless data compression algorithm
Michael Burrows and David J Wheeler. A block-sorting los sless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994
work page 1994
-
[3]
Paolo Ferragina and Giovanni Manzini. Indexing compres sed text. Journal of the ACM , 52(4):552–581, 2005. 6
work page 2005
-
[4]
Optim al-time text indexing in BWT-runs bounded space
Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Optim al-time text indexing in BWT-runs bounded space. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algori thms (SODA), pages 1459–1477. SIAM, 2018
work page 2018
-
[5]
From theory to practice: Plug and play with succinct data structures
Simon Gog, Timo Beller, Alistair Moffat, and Matthias Petr i. From theory to practice: Plug and play with succinct data structures. In Proceedings of the 13th Symposium on Experimental Algorithms (SEA) , pages 326–337. Springer, 2014
work page 2014
-
[6]
Efficient construction of a complete index for pan-g enomics read alignment
Alan Kuhnle, Taher Mun, Christina Boucher, Travis Gagie , Ben Langmead, and Giovanni Manzini. Efficient construction of a complete index for pan-g enomics read alignment. In Pro- ceedings of the 23rd Conference on Research in Computational M olecular Biology (RECOMB) , pages 158–173. Springer, 2019
work page 2019
-
[7]
Fast gapped-read ali gnment with Bowtie 2
Ben Langmead and Steven L Salzberg. Fast gapped-read ali gnment with Bowtie 2. Nature Methods, 9(4):357, 2012
work page 2012
-
[8]
Ultrafast and memory- efficient alignment of short dna sequences to the human genome
Ben Langmead, Cole Trapnell, Mihai Pop, and Steven L Salz berg. Ultrafast and memory- efficient alignment of short dna sequences to the human genome . Genome Biology, 10(3):R25, 2009
work page 2009
Show all 14 references
-
[9]
Fast and accurate short read a lignment with Burrows-Wheeler transform
Heng Li and Richard Durbin. Fast and accurate short read a lignment with Burrows-Wheeler transform. Bioinformatics, 25(14):1754–1760, 2009
2009
-
[10]
The sequenc e alignment/map format and SAMtools
Heng Li, Bob Handsaker, Alec Wysoker, et al. The sequenc e alignment/map format and SAMtools. Bioinformatics, 25(16):2078–2079, 2009
2009
-
[11]
Storage and retrieval of highly repetitive sequence collections
Veli M¨ akinen, Gonzalo Navarro, Jouni Sir´ en, and Niko V¨ alim¨ aki. Storage and retrieval of highly repetitive sequence collections. Journal of Computational Biology , 17(3):281–308, 2010
2010
-
[12]
Two efficient algori thms for linear time suffix array construction
Ge Nong, Sen Zhang, and Wai Hong Chan. Two efficient algori thms for linear time suffix array construction. IEEE Transactions on Computers , 60(10):1471–1484, 2010
2010
-
[13]
ViPR: an op en bioinformatics database and analysis resource for virology research
Brett E Pickett, Eva L Sadat, Yun Zhang, et al. ViPR: an op en bioinformatics database and analysis resource for virology research. Nucleic Acids Research , 40(D1):D593–D598, 2012
2012
-
[14]
Nicola Prezza. r-index. https://github.com/nicolaprezza/r-index, 2018. 7
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.