Back

Accelerating String Comparison in RLZ Compressed Sequences via LCE Jumps

Varki, R.; Boucher, C.

2026-06-16 bioinformatics
10.64898/2026.06.11.731742 bioRxiv
Show abstract

Relative Lempel-Ziv (RLZ) is an effective compression method for large, repetitive collections; however, the fundamental primitives required to elevate it from a passive archival format to a tractable representation for compressed construction have yet to be fully established. In this paper, we introduce an algorithmic framework for structurally comparing and lexicographically sorting sequences of RLZ factors. We characterize when direct factor comparisons are necessary and when they can be bypassed using RLZ specific shortcuts. We further introduce a method for extending truncated factors into right-maximal matches, enabling the recovery of matching statistics from the RLZ parse. Experimentally, RLZ sorting achieved speedups of up to 3.93x over character-based sorting. Together, these results advance the use of the RLZ format as a foundation for compressed construction.

Matching journals

The top 8 journals account for 50% of the predicted probability mass.

1
Bioinformatics
◐ 1204 papers in training set
Top 2%
12.4%
2
Nature Communications
○ 5641 papers in training set
Top 19%
8.9%
3
GigaScience
◐ 212 papers in training set
Top 0.4%
6.7%
4
Genome Biology
○ 637 papers in training set
Top 2%
6.7%
5
Scientific Reports
○ 3612 papers in training set
Top 11%
6.7%
6
PLOS ONE
● 5266 papers in training set
Top 30%
5.1%
7
PLOS Computational Biology
● 1863 papers in training set
Top 10%
3.2%
8
Genome Research
● 468 papers in training set
Top 2%
3.2%
50% of probability mass above
9
Nature Methods
○ 385 papers in training set
Top 3%
3.2%
10
Proceedings of the National Academy of Sciences
● 2444 papers in training set
Top 17%
3.2%
11
Algorithms for Molecular Biology
○ 17 papers in training set
Top 0.1%
3.2%
12
Nature Biotechnology
○ 172 papers in training set
Top 2%
1.7%
13
iScience
○ 1154 papers in training set
Top 17%
1.7%
14
IEEE Transactions on Computational Biology and Bioinformatics
● 20 papers in training set
Top 0.3%
1.7%
15
Nucleic Acids Research
◐ 1281 papers in training set
Top 9%
1.7%
16
BioData Mining
○ 22 papers in training set
Top 0.3%
1.5%
17
Bioinformatics Advances
◐ 203 papers in training set
Top 3%
1.5%
18
Computational and Structural Biotechnology Journal
● 242 papers in training set
Top 4%
1.5%
19
Nature Computational Science
○ 55 papers in training set
Top 0.8%
1.4%
20
Patterns
○ 78 papers in training set
Top 2%
1.4%
21
IEEE Access
● 35 papers in training set
Top 1.0%
1.1%
22
Journal of Computational Biology
○ 48 papers in training set
Top 0.8%
1.1%
23
BMC Bioinformatics
○ 457 papers in training set
Top 5%
1.1%
24
Cell Systems
○ 201 papers in training set
Top 3%
1.1%
25
PeerJ
◐ 308 papers in training set
Top 9%
1.0%
26
Advanced Science
○ 286 papers in training set
Top 8%
1.0%
27
NAR Genomics and Bioinformatics
◐ 242 papers in training set
Top 4%
0.8%
28
Communications Biology
○ 993 papers in training set
Top 30%
0.8%
29
eLife
● 5828 papers in training set
Top 69%
0.6%
30
Journal of Chemical Information and Modeling
● 238 papers in training set
Top 3%
0.6%