# OReO: optimizing read order for practical compression

Mathilde Girard, Léa Vandamme, Bastien Cazaux, Antoine Limasset

► To cite this version:

Mathilde Girard, Léa Vandamme, Bastien Cazaux, Antoine Limasset. OReO: optimizing read order for practical compression. Bioinformatics Advances, 2025, 5 (1), 10.1093/bioadv/vbaf128. hal-05396215

HAL Id: hal-05396215

https://hal.science/hal-05396215v1

Submitted on 3 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Sequence analysis

OReO: optimizing read order for practical compression

Mathilde Girard<fnref n="1" />,*, Léa Vandamme<fnref n="1" />, Bastien Cazaux<fnref n="1" />, Antoine Limasset<fnref n="1" />

**Abstract**

**Motivation:** Recent advances in high-throughput and third-generation sequencing technologies have created significant challenges in storing and managing the rapidly growing volume of read datasets. Although more than 50 specialized compression tools have been developed, employing methods such as reference-based approaches, customized generic compressors, and read reordering, many users still rely on common generic compressors (e.g. gzip, zstd, xz) for convenience, portability, and reliability, despite their low compression ratios. Here, we introduce Optimizing Read Order (OReO), a simple read-reordering framework that achieves high compression performance without requiring specialized software for decompression. By grouping overlapping reads together before applying generic compressors, OReO exploits inherent redundancies in sequencing data and achieves compression ratios on par with state-of-the-art tools. Moreover, because it relies only on standard decompressors, OReO avoids the need for dedicated installations and maintenance, removing a key barrier to practical adoption.

**Results:** We evaluated OReO on both Oxford Nanopore Technologies (ONT) and HiFi genomic and metagenomic datasets of varying sizes and complexities. Our results demonstrate that OReO provides substantial compression gains with comparable resource usage and outperforms dedicated methods in decompression speed. We propose that future compression strategies should focus on reordering as a means to let generic compression tools fully exploit data redundancy, offering an efficient, sustainable, and user-friendly solution to the growing challenges of sequencing data storage.

**Availability and implementation:** The OReO code is open source and available at github.com/girunivlille/oreo.

# 1 Introduction

Over the past decade, high-throughput sequencing technologies have transformed sequence bioinformatics into one of the most data-intensive scientific fields. Modern sequencers can now generate tens of terabases of data per day, enabling unprecedented scientific discoveries while simultaneously creating formidable challenges in data management and storage. Public repositories such as the Sequence Read Archive and the European Read Archive reflect this explosive growth as they already house over 60 petabases of data, and these archives continue to expand at an accelerating pace. Despite the inherent redundancy in most sequencing data, their compression remains nontrivial for several reasons. First, the sheer volume of reads necessitates handling extremely large files. Second, shared sequences are often dispersed throughout a dataset, making it difficult for compressors to retain the massive context needed to exploit these redundancies. Third, sequencing errors introduce noise that hampers the detection of common subsequences and they themselves are relatively incompressible. Consequently, generic compressors frequently struggle to achieve better than a four-fold reduction, effectively storing each nucleotide in two bits. In response, researchers have developed a plethora of specialized methods to handle the unique properties of sequencing data, which can be broadly categorized as follows: Tuned generic compressors, Reference-based compressors, and Reordering-based compressors.

## 1.1 Tuned generic compressors

A number of specialized tools build upon established compression techniques but tailor them to the distinctive characteristics of sequencing data. For instance, DSRC (Deorowicz and Grabowski 2011), BIND (Bose et al. 2012), and DELIMINATE (Mohammed et al. 2012) employ a LZ77-style dictionary to capture recurring patterns within large datasets, while Fastqz (Bonfield and Mahoney 2013), LFQC (Nicolae et al. 2015), and LFastqC (Al Yami and Huang 2019) leverage the PAQ compressor family. Similarly, Fqzcomp (Bonfield and Mahoney 2013) and GTZ (Xing et al. 2017) take advantage of arithmetic coding, and Fqzcomp additionally includes a *k*-mer model to predict subsequent nucleotides, thereby improving compression efficiency. Other tools incorporate hybrid strategies tailored to specific components of the FASTQ format (headers, sequences, and quality scores), as seen in kungfq (Grassi et al. 2012), DSRC2 (Roguski and Deorowicz 2014), and FQC (Dutta et al. 2015). G-SQZ (Tembe et al. 2010) applies Huffman encoding by associating each base with its corresponding quality value, whereas NAF (Kryukov et al. 2019) takes advantage of modern compressors such as zstd. Some approaches, notably MFcompress (Pinho and Pratas 2014), rely on multiple competing finite-context models to efficiently capture both nucleotide and quality information. Finally, SolidZipper (Jeon et al. 2011) and SeqDB (Howison 2013) prioritize decompression speed by employing interleaved block

<footnote n="1">¹Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France</footnote>

<footnote>*Corresponding author. Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France.</footnote>

<footnote>E-mail: girardmathilde2000@gmail.com.</footnote>

<footnote>Associate Editor: Thomas Lengauer</footnote>
compression, demonstrating that tuned compressors can com-
bine compactness with practical performance characteristics.

1.2 Reference-based approaches

A second major class of tools exploits the fact that most reads
can be aligned to a known reference genome, thereby encod-
ing only positions and discrepancies. This strategy can be ex-
tremely space-efficient when the selected reference closely
matches the read set. However, it also has inherent con-
straints: a suitable reference may be unavailable (e.g. for
metagenomic datasets or previously unsequenced organisms),
or it may be insufficiently similar if the organism exhibits
high polymorphism. Moreover, compression methods that
rely on an external reference can be cumbersome to decom-
press unless the reference is stored within the compressed file,
which itself increases file size. Several tools rely on such
alignment-based compression. For example, Gencompress
(Daily et al. 2010), CRAM (Fritz et al. 2011), Fastqz
(Bonfield and Mahoney 2013), and FQZip (Zhang et al.
2015a) map each read to a known reference, storing only the
variations. Other methods, such as SlimGene (Kozanitis et al.
2010), SamZIP (Sakib et al. 2011), NGC (Popitsch and von
Haeseler 2013), Gobi (Campagne et al. 2013), and LW-
FQZip (Zhang et al. 2015b), compress the SAM files result-
ing from these alignments. More recent tools propose
advanced strategies, HUGO (Kingsford and Patro 2015) han-
dles unmapped reads by searching across multiple reference
genomes, while Deez (Hach et al. 2014) locally assembles
unmapped reads before compressing them. BARCODE
(Rozov et al. 2014) avoids the explicit mapping step by
inserting reads into a Bloom filter cascade and using the refer-
ence sequence to query these filters. Meanwhile, kpath
(Kingsford and Patro 2015) uses the reference to build a de
Bruijn graph and encode reads according to the paths they
traverse in the graph. Interestingly, some tools implement “de
novo” versions of reference-based compression by construct-
ing their own internal references. Quip (Jones et al. 2012),
for instance, builds a reference sequence directly from the in-
put data and maps reads to it, whereas Leon (Benoit et al.
2015) generates a probabilistic de Bruijn graph as a surrogate
reference and encodes reads accordingly. These adaptations
expand the applicability of reference-based methods by miti-
gating some of the practical drawbacks associated with exter-
nal reference genomes.

1.3 Reordering approaches

A third family of compression strategies leverages the fact
that the order of reads in most sequencing datasets is unim-
portant to downstream analyses. By rearranging reads so that
overlapping or highly similar sequences are placed in close
proximity, these methods enable more efficient “local” pat-
tern detection without requiring compressors to maintain a
large global context. Although some downstream analysis as-
sume uniform read distributions that could be hindered by
such reordering, this can be fixed after decompression by
shuffling the reads. Many tools implement reordering-based
compression. Coil (White and Hendy 2008) and Recoil
(Yanovsky 2011) cluster reads with significant suffix–prefix
overlaps, while BEETLE (Cox et al. 2012) optimizes the read
order for Burrows-Wheeler Transform (BWT)-based com-
pression. Scalce (Hach et al. 2012) applies Locally Consistent
Parsing (LCP) to improve the performance of generic com-
pressors like gzip. ORCOM (Grabowski et al. 2015) and

Mince (Patro and Kingsford 2015) organize reads according
to minimizers, a concept extended by BdBG (Wang et al.
2018) via path-encoding strategies that echo those of Quark
and Leon. Meanwhile, Harc (Chandak et al. 2018) and
Minicom (Liu et al. 2019) reorder reads according to contigs
assembled from the input, and Assembltrie (Ginart et al.
2018) constructs a “read forest” reference to guide reorder-
ing. Fastore (Roguski et al. 2018) combines initial minimizer-
based binning with a final ordering pass reminiscent of Harc,
and FQSqueezer (Deorowicz 2020) relies on a k-mer dictio-
nary to implement a dynamic Markov coder for partial-
matching predictions. PgRc (Kowalski and Grabowski 2020)
approximates a shortest common superstring to serve as a
central reference [with a GPU-based variant provided by
CURC (Xie et al. 2022)], while Mstcom (Liu and Li 2021)
attempts to construct a minimum spanning tree to represent
how reads can be differentially encoded. Finally, Quark
(Sarkar and Patro 2017) proposes a semi-reference-based
strategy, in which a reference is required only during com-
pression but not decompression. Collectively, these
approaches illustrate how optimized read reordering can dra-
matically improve compression efficiency by amplifying local
sequence similarity.

1.4 Related work

Although most compression efforts focus on a single read set,
some methods exploit shared redundancy by co-compressing
multiple *related* datasets. For example, DARRRC (Holley
et al. 2018) encodes a de Bruijn graph with Bloom filters to
jointly compress many datasets, while PMFFRC (Sun et al.
2023) uses clustering of reads from different collections to op-
timize co-compression. MRC (Tang and Li 2021) applies
unsupervised learning for similar purposes, and Mizar (Pratas
and Pinho 2024) groups metagenomic datasets prior to com-
pression by leveraging taxonomic assignment. Outside the
main scope of this work, some tools adopt a *lossy* paradigm,
where certain bases are altered to improve compressibility.
Because stochastic sequencing errors are inherently costly to
represent, fixing them can reduce file size significantly. BFQzip
(Guerrini et al. 2022), for instance, modifies bases to improve
compression efficiency, demonstrating that lower error rates
typically enable better compression, albeit at the potential cost
of introducing analysis bias. A final, extensive line of research
focuses on *quality scores*, which can be difficult to compress
yet are useful for some downstream tasks as genotyping.
Several studies demonstrate that discretizing (Wan et al. 2012)
quality scores can yield substantial compression gains with
only a minimal effect on downstream analysis. However, those
subjects lie beyond the scope of our present discussion.

1.5 Long reads

At the onset of third-generation sequencing technologies,
long-read datasets were relatively rare and offered lower cov-
erage, in large part due to higher costs. In addition, error
rates exceeding 10% posed extra challenges for compression
by introducing substantial noise, making these datasets less
amenable to efficient encoding. However, with recent cost
reductions and error rates now approaching those of second-
generation sequencing platforms (Bankevich et al. 2022,
Sanderson et al. 2023), the compression of long-read data
has become increasingly relevant, and several new tools have
emerged to address this need. ENANO (Dufort y Álvarez
et al. 2020) is a tuned generic compressor relying on
arithmetic encoding. RENANO (Dufort y Álvarez et al. 2021) is more closely aligned with reference-based strategies but operates both with and without an external reference by performing de novo assembly of the input reads to compen- sate for its absence. NANOSPRING (Meng et al. 2023) fol- lows a similar approach, using MinHash sketches to assemble the reads and then encoding them according to the constructed reference. Because the reads are reordered based on their positions in the assembled contigs, NANOSPRING is also related to reordering-based methods. Other reordering-based compressors include FastqCLS (Lee and Song 2022), which reorders reads based on nucleotide distri- bution rather than overlap, and Colord (Kokot et al. 2022), which computes *k*-mer similarity among reads to encode them relative to one another. Interestingly, when these com- pressors internally reorder the reads, they typically record the original order so that the file can be reconstructed exactly upon decompression. This approach diverges somewhat from standard second-generation sequencing (NGS) compression, largely because the overhead for storing positions is relatively small: preserving the order of *N* reads requires about *N*log(*N*) bits. For example, in a large mammalian dataset with 10 million reads of length 10 kb (totaling 100 gigabases), storing the positions with 32-bit integers amounts to approxi- mately 40 MB, which can be reduced to around 30 MB using entropy-based compression. This overhead is minimal when compared to the total data volume. Furthermore, as read lengths increase, fewer total reads are necessary to cover the same number of bases, which further diminishes the storage costs associated with preserving their original order.

## 1.6 Going beyond dedicated compressors

A high-level comparison of the three main compression para- digms reveals that reference-based methods generally achieve impressive compression ratios but depend on an external refer- ence, tuned generic compressors can operate *de novo* albeit at lower efficiency, and reordering approaches appear to offer the best of both worlds by providing strong compression without relying on a reference. In this article, we address the critical issue of dedicated compressors: although more than 50 specialized compression tools have been developed, their actual impact on day-to-day data storage and handling remains minimal. Instead, end users typically rely on generic compressors like gzip, zstd, or xz. Several factors contribute to this preference:

* **Ease of use:** Generic tools require no additional installa- tions or configuration steps.

* **Portability:** These tools are readily available on all major operating systems and High-Performance Computing (HPC) environments.

* **Compatibility:** Generic compressed files are easily handled by other tools and workflows due to widely available C++ and Python libraries.

* **Maintainability:** Many academic compressors lack ongo- ing support and updates, whereas generic tools are main- tained and validated by large communities.

Given these barriers, we propose a shift in perspective: rather than developing yet another custom compressor, *we improve the datasets compressibility* for existing generic tools. Specifically, we rely on well-established reordering techniques to rearrange reads such that those sharing similar- ities are placed in close proximity, thereby producing

semantically equivalent files that are much more amenable to generic compression. Focusing on *pre-compression*, i.e. pre- processing the data before applying a standard compressor, offers several advantages. First, using widely accessible tools eliminates concerns about software availability, reliability, and long-term maintenance. Second, as we will show, this ap- proach can deliver compression ratios comparable to state- of-the-art dedicated methods, representing an enormous gain over naive usage of generic compressors. Third, while generic compressors often provide fast decompression, reordering pre-processing can further enhance decompression through- put in some scenarios and vastly outperform dedicated com- pressors. In the following, we introduce a proof-of-concept tool, OReO, which reorders reads based on a draft assembly graph. Our design emphasizes simplicity and modularity, leveraging a Python implementation that integrates well- known, tunable third-party utilities. This highlights that reor- dering long reads need not be inherently complex and that straightforward methods can yield excellent results. We then benchmark OReO against specialized long-read compressors (NanoSpring and CoLoRd) and generic tools (gzip, zstd, bzip2, and xz), both with and without reordering, on geno- mic and metagenomic data with both Oxford Nanopore Technologies (ONT) and HiFi datasets spanning various ge- nome sizes and complexities. We did not include compressors based on short-read reordering, as they assume all reads have the same length, an assumption that does not hold in our long-read datasets. In addition, we excluded FastqCLS, as its compression performance is effective only on FASTQ format datasets and performs poorly on FASTA files compared to NanoSpring and Colord after being tested on our datasets. Our experiments show that generic compressors, when cou- pled with reordering, can achieve near state-of-the-art com- pression rates alongside fast decompression. Finally, we examine potential ways to improve resource usage and file- size efficiency, drawing on earlier research into compression- resource trade-offs.

# 2 Method

## 2.1 High-level overview

We introduce OReO, a tool that reorders FASTA long-read files so that reads with overlapping sequences appear in close proximity (see Fig. 1). By approximating their natural geno- mic arrangement, OReO ensures that overlapping reads, which share substantial subsequences, are placed nearby. In practice, this strategy enhances generic compression tools, as they can more efficiently exploit local redundancies. Because reordering alone does not modify any sequence data, the resulting compression can be considered lossless. Moreover, OReO does not depend on a specialized compression format, nor does it require an external reference genome. These fea- tures make it straightforward to integrate OReO into existing workflows and to pair it with standard, well-maintained compressors already familiar to most users.

OReO follows three main steps to sort a file (see Fig. 2):

1) *Genome assembly*—generate a contig graph from in- put reads,

2) *Contigs ordering*—use a graph traversal to or- der contigs,

3) *Read placement*—order reads using the order of contigs obtained and the positions of reads on each contig.
<figure><img src="image_2.png" /><figcaption>**Figure 1.** OReO's use case contrasted with specialized compression tools.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Figure 2.** Overview of OReO's reordering process for long-read data. The workflow involves (1) generating a contig graph, (2) traversing this graph to determine the order of contigs, and (3) reordering reads according to their positions on each contig.</figcaption></figure>

The output file contains the same reads as the input and can then be compressed with any generic compressor.

## 2.2 Genome assembly

Constructing a *de novo* assembly and mapping the reads to it is arguably the most straightforward method to order reads by their mutual relationships, and this approach has been employed by multiple tools for both second- and third-generation sequencing datasets. Numerous long-read assemblers are available in the literature, which aim to produce high-quality, error-free genomes but often demand substantial runtime and memory resources. Here, our goal is merely to obtain an approximate, “noisy” assembly that allows us to map and order the reads effectively, rather than to produce a biologically accurate consensus sequence. Consequently, high precision is not essential, and we prioritize speed over accuracy. We therefore adopt miniasm (Li 2016), a simple string graph assembler that avoids expending computational resources on complex repeat resolution or error correction. In OReO, the required all-versus-all alignments are carried out using minimap2 (Li 2016). Because OLC-based assemblies can become expensive at very high coverage, the user may optionally specify a subsampled set of reads (ideally 30–60×) to reduce both runtime and resource usage during assembly. Including at least 30× coverage of the longest reads is recommended to ensure that the resulting assembly remains sufficiently contiguous. Miniasm ultimately produces contigs

in FASTA format, which serve as the basis for aligning and ordering the full set of reads. Practically, parameters for both minimap2 and miniasm can be tuned to account for specific read properties (e.g. length or error rate), optimizing memory usage and runtime without compromising assembly contiguity. Nonetheless, we report OReO's performance under its default settings, reported in the appendix, to illustrate its baseline capabilities.

## 2.3 Contig ordering

Ideally, the assembly process yields a small number of long, continuous contigs, thereby gathering reads that overlap one another in close proximity. However, unresolved repeats often cause assemblers to split the genome into multiple contigs. Typically, these contigs are output as an oriented graph in GFA format, where edges represent overlaps between contigs. Since reads sharing common subsequences end up in the same contig, and their divergent regions connect to other contigs, bringing linked contigs together also clusters overlapping reads. From contig connections, OReO reconstructs the contig graph and then employs a depth-first search (DFS) to traverse and order the contigs. DFS follows each path to its end before backtracking and exploring any remaining branches. This ensures that continuity between contigs is maintained wherever possible, while still including all contigs in the final ordering. The outcome is a contig order that reflects possible paths within the assembly graph, thereby
grouping together reads with strong sequence similarity. In
turn, these localized similarities improve the performance of
subsequent compression steps, as reads that share overlap-
ping regions are located closer to one another in the reor-
dered file.

## 2.4 Read placement and ordering

To place reads in the final output file, they are first mapped
onto the assembled contigs with minimap2. The resulting PAF
file contains, among other details, the read and contig identi-
fiers, the mapping start position on the contig, and the relative
strand. OReO then sorts this PAF file by contig, and within
each contig, by mapping start position. To generate the final
ordered read set, OReO iterates through the contigs in the or-
der determined by the assembly graph traversal. For each con-
tig, it retrieves the associated reads from the sorted PAF file
and writes them in ascending order of their alignment posi-
tions. Each read appears only once, the first time it is encoun-
tered. Unmapped reads that are missing from the PAF file are
simply appended at the end of the output. The end result is a
FASTA file that contains all input reads, but in an arrange-
ment that places overlapping or similar reads close together.

## 2.5 Read orientation

By default, OReO writes all reads in the same orientation rel-
ative to their contig alignments. This choice is motivated by
the fact that two reads, which originate from the same geno-
mic region but are oriented differently, will compress poorly.
Converting one read to the other's orientation leads to more
extensive redundancy, thereby enhancing compressibility.
Moreover, a read and its reverse complement encode essen-
tially the same information, since each strand represents the
same DNA fragment. However, in certain analyses, such as
the detection of strand-specific sequencing errors or struc-
tural variants, orientation can be biologically meaningful. To
accommodate such use cases, OReO offers an option to pre-
serve the original strand orientation. In this mode, each
strand is handled as a different sequence: the mapping file is
firstly separated by alignment strand orientation, then by
contig and mapping position. As a result, reads that map to
the reverse strand are neither reversed nor complemented;
they remain in their original sequencing format. Because
these orientation changes only affect how reads are repre-
sented, they are fully reversible if one maintains a small auxil-
iary file to track the original positions and orientations. For
instance, an input with 10 million 10 kb reads would require
storing a single integer (32 bits) per read to track read posi-
tion (roughly 32 MB) and a single bit per read for orientation
(roughly 1 MB). In practice, this overhead is minimal com-
pared to the typical size of modern sequencing datasets.

# 3 Results

## 3.1 Experimental setup

All experiments were conducted on a single cluster node
equipped with an Intel(R) Xeon(R) Gold 6130 CPU @
2.10 GHz, 128GB of RAM, and running Ubuntu 22.04.

## 3.2 Dataset descriptions

Escherichia coli

HiFi: SRR11434954, 1.8M reads, 23.1 Gb (5000×). ONT: SRR28370668, 6.8M reads, 9.1 Gb (2000×).

Arabidopsis thaliana

HiFi: SRR14728885, 1.5M reads, 22.9 Gb (170×). ONT: SRR14739179, 3M reads, 56.8 Gb (420×).

Human

HiFi: SRR29483063-5, 11.4M reads, 194.1 Gb (60×).
ONT: SRR23365080, 7.5M reads, 352 Gb (113×).

Zymo (Microbial Community)

HiFi: SRR13128014 (21 strains, 17 species), 2M reads, 18 Gb.

To better reflect commonly encountered coverage depths,
we used the longest 100× reads (both HiFi and ONT) for
*E. coli* and *A. thaliana*. For performance reasons, the human
datasets were capped at 50×. Because the Zymo dataset fea-
tures uneven coverage, the same subsampling strategy was in-
applicable; thus, its results are also presented only in the
Appendix. All results presented were processed on files in
FASTA format.

## 3.3 Compressed size

As an initial experiment presented in Fig. 3, we applied com-
monly used generic compressors (gzip, bzip2, xz, and zstd) to
subsampled datasets from *E. coli*, *A. thaliana*, and humans,
both *before* and *after* OReO reordering. Each compressor
was tested across all available compression levels. We also
evaluated the state-of-the-art compressors NanoSpring and
CoLoRd; however, because these tools employ their own in-
ternal reordering strategies, OReO ordering does not affect
them, so we report their performance only on the original,
unreordered datasets. Surprisingly, although NanoSpring is
intended to be lossless, its output file did not include the orig-
inal read headers. Consequently, the comparison may not be
entirely fair. Several observations can be made:

* gzip is widely used but often provides the lowest compres-
  sion. With HiFi data, higher compression levels benefit
  from OReO ordering, though the effect is modest; for
  noisier ONT data, the improvement is barely noticeable.
  This suggests that gzip's relatively small compression win-
  dow rarely spans enough reads to exploit redundancy
  effectively.

* bzip2 sees a consistent, albeit slight, improvement from OReO across all levels. Its overall compression ratio, however, remains less competitive than that of other compressors.

* xz is the only tool that achieves notable compression on the original datasets, especially for smaller genomes, indicating its ability to handle large contexts at higher compression levels. OReO substantially boosts its performance, even surpassing dedicated compressors at some high compression settings.

* zstd is less effective than xz on regular files, but delivers similar results on OReO-optimized files and can match or exceed dedicated compressors in some cases.

* Noise level As expected, the noisier ONT data are more challenging than their HiFi matches for all compressors.

Taken together, these results demonstrate that reordering
can significantly enhance the performance of generic
<figure><img src="image_4.png" /><figcaption>**Figure 3.** Comparison of file compression using various compressors and compression levels, both with and without OReO ordering, alongside CoLoRd and NanoSpring on (A) HiFi and (B) ONT datasets.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 4.** Decompression time benchmarks for 100x *E. coli*, *A. thaliana*, and *Human* datasets on (A) HiFi and (B) ONT.</figcaption></figure>

compression tools, occasionally matching or even outperforming specialized methods.

## 3.4 Decompression efficiency

We next evaluated the *decompression* performances in Fig. 4, which is often considered of higher practical importance than compression speed because files tend to be compressed only once but may be decompressed multiple times. In most cases, OReO-processed files decompress faster, sometimes by several-fold, particularly with xz and zstd. Moreover, generic decompressors operate considerably faster than dedicated decompressors, occasionally by an order of magnitude. Notable exceptions are bzip2, which can be slower than

specialized tools and xz at lower compression levels. Overall, these observations highlight another practical benefit of relying on generic (de)compressors in conjunction with reordering: not only do they achieve competitive compression ratios, but they also offer consistently higher decompression speeds in everyday usage. RAM usage during decompression, reported in the appendix, shows that all generic compression tools exhibit negligible memory usage (<100MB), Colord displays low memory usage at decompression (<1GB) while NanoSpring can display high memory usage.

## 3.5 Compression efficiency

In a third experiment, we evaluated the computational cost of various compression strategies and compared it with the
<figure><img src="image_6.png" /><figcaption>**Figure 5.** Compression time versus compressed file size for the human (A) HiFi dataset and (B) ONT dataset for initials and sorted files, with all compression levels. Preprocessing time is included by a dot for each sorted file compressed with the highest compression level.</figcaption></figure>

resulting compression ratio. We present these results for the humans datasets in Fig. 5, and the other datasets can be found in the appendix. Across most datasets, reordering with OReO did not increase compression time; in some instances, it slightly reduced it, and in others, it led to a significant compression speed-up. Overall, all tools show rapid compression at lower settings, while higher gzip and zstd levels incur greater costs, and xz becomes especially expensive at its maximum setting. Despite the computational overhead of the required de novo assembly, combining OReO with a generic compressor generally results in faster runtimes than specialized tools like CoLoRd and NanoSpring. The only exception observed in our tests was the Human HiFi dataset. Detailed timing results are provided in the Appendix. RAM usage during compression, reported in the appendix, shows that all generic compressors display low memory usage (<1GB), while dedicated compressors and OReO can display high memory usage.

## 3.6 Impact of read orientation on compression

Although reordering reads greatly improves compression for generic tools, strand orientation also plays an important role. To illustrate this, we compared three variants of OReO in Fig. 6:

1) Optimizing both ordering and strand, i.e. reordering reads and unifying their orientation (best compression).

2) Optimizing only ordering while preserving strand, i.e. reads remain in their original orientation but are reordered along other reads from the same strand (best choice when strand is biologically relevant).

3) Optimizing only ordering without accounting for strand divergence, i.e. ignoring strandness (worst compression).

Our results show that combining both strand unification and read ordering delivers the highest compression gains. When users wish to preserve the original strand, ordering
<figure><img src="image_7.png" /><figcaption>**Figure 6.** Comparison of three strategies for managing reverse-complement reads and their impact on compression efficiency. **Variant 1 (OReO default)** reorders reads and, when beneficial, reverse-complements them to maximize compression. **Variant 2** preserves the original read orientation, grouping same-strand reads together (OReO's behavior when strand information must be retained). **Variant 3** reorders reads without considering their strand, typically resulting in lower compression efficiency.</figcaption></figure>

each strand separately still yields considerable improvement, but neglecting strand orientation altogether can lead to degraded compression performance. Consequently, explicitly managing the reads strands, whether by unifying or separating them, must be factored in when using generic compressors, which (unlike most sequence analysis tools) do not inherently account for strand orientation.

## 3.7 Compressed index boosting

Beyond improving overall compression, OReO's read reordering can also enhance indexing structures that rely on internal compression. One example is the K2R ($k$-mer to reads) index (Vandamme et al. 2025), which associates each $k$-mer with a compressed list of read identifiers containing that $k$-mer. With well-ordered reads, $k$-mers tend to be shared by neighboring reads, making their corresponding identifier lists more amenable to compression techniques such as delta encoding. To demonstrate this effect, we used K2R to index the previously described datasets with and without OReO preprocessing. As shown in Table 1, OReO's reordering substantially improved both the index size and the construction runtime. Such properties could be leveraged in future index designs that aim to take full advantage of these overlapping and proximity-based features.

## 4 Future work

In this work, we presented OReO, a straightforward proof-of-concept tool that reorders reads according to a draft assembly before applying generic compressors. Despite its simplicity, this approach achieves compression ratios on par with state-of-the-art dedicated tools, yet requires comparable resources and offers faster and lighter decompression. We also demonstrated that such read ordering can improve the efficiency of certain index structures. We hope these results will encourage future developers to focus on read-reordering strategies rather than producing yet another specialized compressor, and to highlight for users that reordering offers

<table><caption>**Table 1.** K2R time usage and index size on various input file.</caption><thead><tr><th>Dataset</th><th></th><th>Time (s)</th><th>Index (MB)</th></tr></thead><tbody><tr><td>E. coli HiFi</td><td>Initial/OReO</td><td>114/100</td><td>60/40</td></tr><tr><td>E. coli ONT</td><td>Initial/OReO</td><td>112/103</td><td>60/13</td></tr><tr><td>A. Thaliana HiFi</td><td>Initial/OReO</td><td>3197/2805</td><td>1781/367</td></tr><tr><td>A. Thaliana ONT</td><td>Initial/OReO</td><td>3924/3777</td><td>2685/2185</td></tr><tr><td>Human HiFi</td><td>Initial/OReO</td><td>21 951/22 625</td><td>6959/1731</td></tr><tr><td>Human ONT</td><td>Initial/OReO</td><td>36 718/38 302</td><td>6997/5095</td></tr></tbody></table>

substantial disk-space savings with almost no drawbacks. To provide assurances about data fidelity, we supply a built-in consistency check (similar to an MD5 hash) confirming that the reordered file preserves exactly the same sequences (or their canonical forms, if strand orientations are allowed to change). Additionally, an optional file storing the original read order and strand allows users to restore the input file if desired. The major limitation of our proposed workflow is its relatively high resource usage due to multiple read-mapping steps. In particular, the all-versus-all read comparison used for overlap-based assembly can be prohibitively costly and may not be necessary. Recent advances in genome assembly demonstrate that accurate drafts of long-read datasets can be generated without constructing overlap graphs, for example, by using de Bruijn-based frameworks with large $k$-mers or minimizer-based de Bruijn graphs (Ekim et al. 2021). One such approach, RMDBG (Ekim et al. 2021), was evaluated in our experiments but produced contigs too fragmented for our use case. A purpose-built greedy assembler, designed to prioritize computational efficiency over biological precision, could significantly reduce resource requirements. A second obstacle arises from the read-mapping step on the resulting draft assembly. This step recovers contig-read associations that the assembler itself already computes internally. Although tools like miniasm track some read information, they only retain data for the subset of reads used in assembly, discarding shorter reads. A custom assembler that explicitly records all read-contig links could eliminate the need for this secondary mapping step entirely. Beyond our current workflow, several alternative strategies could be explored. One possibility is a shortest-common-superstring approach, adapted to handle the intrinsic noise of raw reads. Methods that rely purely on sequence similarity, such as those using small $k$-mers, MinHash sketches, or minimizers, could also cluster reads more directly and potentially lower computational demands. However, despite its high resource requirements, OReO outperforms state-of-the-art tools in terms of speed on most datasets. Additionally, after just one run of OReO per dataset, the end user can make unlimited use of generic compressors and decompressors, benefiting from their low resource consumption. Another promising direction involves incorporating read-correction methods, which reduce noise in the input data and improve overall compression ratios. Nonetheless, some users are wary of error-correction tools because of the risk of introducing bias. A potential compromise is to store the differences between original and corrected reads, allowing the reconstruction of uncorrected reads. Even if these differences are difficult to compress, the rest of the data could benefit from significantly enhanced compressibility. The viability of this scheme, and whether its complexity is justified, remains an open question. Another way of improving compression ratios is to sort the unmapped reads. As shown in the appendix, unmapped reads represent only a
small proportion of total reads in our datasets, so only a slight improvement is expected. However, we tested samtools sort with the option "-M" to sort unmapped reads on one dataset and included the results in the appendix. The gain is indeed slight and time cost is too high to adopt this method in practice in our current implementation. Also, the alignment-free methods mentioned earlier would eliminate the need to manage these reads. A possible further work is the management of FASTQ files. While OReO can sort FASTQ files, the compression benefit is less significant compared to FASTA files due to the incompressibility of quality scores. Improving FASTQ compression could involve extracting quality scores placed in the same order as their corresponding sequences, and compressing them separately, with or without loss. Finally, the co-compression of multiple similar datasets has yet to be explored for long reads. This represents an exciting challenge: developing methods to compress large collections of related files together while still enabling selective decompression of individual datasets without unpacking the entire collection.

## Conflict of interest

None declared.

## Funding

This work is supported by the French National Research Agency AGATE ANR-21-CE45-0012.

## Data availability

The identifiers of the SRA datasets that were used in the experiments are listed at the beginning of the Results section. The OReO code is open source and available at github.com/girunivlille/oreo.

## References

* Al Yami S, Huang C-H. LFastqC: a lossless non-reference-based FASTQ compressor. *PLoS One* 2019;14:e0224806.

* Bankevich A, Bzikadze AV, Kolmogorov M *et al.* Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads. *Nat Biotechnol* 2022;40:1075–81.

* Benoit G, Lemaitre C, Lavenier D *et al.* Reference-free compression of high throughput sequencing data with a probabilistic de Bruijn graph. *BMC Bioinformatics* 2015;16:288–14.

* Bonfield JK, Mahoney MV. Compression of FASTQ and SAM format sequencing data. *PLoS One* 2013;8:e59190.

* Bose T, Mohammed MH, Dutta A *et al.* Bind: an algorithm for loss-less compression of nucleotide sequence data. *J Biosci* 2012;37:785–9.

* Campagne F, Dorff KC, Chambwe N *et al.* Compression of structured high-throughput sequencing data. *PLoS One* 2013;8:e79871.

* Chandak S, Tatwawadi K, Weissman T. Compression of genomic sequencing reads via hash-based reordering: algorithm and analysis. *Bioinformatics* 2018;34:558–67.

* Cox AJ, Bauer MJ, Jakobi T *et al.* Large-scale compression of genomic sequence databases with the burrows-wheeler transform. *Bioinformatics* 2012;28:1415–9.

* Daily K, Rigor P, Christley S *et al.* Data structures and compression algorithms for high-throughput sequencing technologies. *BMC Bioinformatics* 2010;11:514–2.

* Deorowicz S. FQSqueezer: k-mer-based compression of sequencing data. *Sci Rep* 2020;10:578.

* Deorowicz S, Grabowski S. Compression of DNA sequence reads in FASTQ format. *Bioinformatics* 2011;27:860–2.

* Dufort y Álvarez G, Seroussi G, Smircich P *et al.* ENANO: encoder for NANOpore FASTQ files. *Bioinformatics* 2020;36:4506–7.

* Dufort y Álvarez G, Seroussi G, Smircich P *et al.* RENANO: a reference-based compressor for NANOpore FASTQ files. *Bioinformatics* 2021;37:4862–4.

* Dutta A, Haque MM, Bose T *et al.* FQC: a novel approach for efficient compression, archival, and dissemination of FASTQ datasets. *J Bioinform Comput Biol* 2015;13:1541003.

* Ekim B, Berger B, Chikhi R. Minimizer-space de Bruijn graphs: whole-genome assembly of long reads in minutes on a personal computer. *Cell Syst* 2021;12:958–68.e6.

* Fritz MH-Y, Leinonen R, Cochrane G *et al.* Efficient storage of high throughput DNA sequencing data using reference-based compression. *Genome Res* 2011;21:734–40.

* Ginart AA, Hui J, Zhu K *et al.* Optimal compressed representation of high throughput sequence data via light assembly. *Nat Commun* 2018;9:566.

* Grabowski S, Deorowicz S, Roguski Ł. Disk-based compression of data from genome sequencing. *Bioinformatics* 2015;31:1389–95.

* Grassi E, Di Gregorio F, Molineris I. KungFQ: a simple and powerful approach to compress FASTQ files. *IEEE/ACM Trans Comput Biol Bioinform* 2012;9:1837–42.

* Guerrini V, Louza FA, Rosone G. Lossy compressor preserving variant calling through extended BWT. In: *Proceedings of the 15th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC 2022)—BIOINFORMATICS*, pp. 38–48. INSTICC, SciTePress, 2022.

* Hach F, Numanagić I, Alkan C *et al.* SCALCE: boosting sequence compression algorithms using locally consistent encoding. *Bioinformatics* 2012;28:3051–7.

* Hach F, Numanagic I, Sahinalp SC. DeeZ: reference-based compression by local assembly. *Nat Methods* 2014;11:1082–4.

* Holley G, Wittler R, Stoye J *et al.* Dynamic alignment-free and reference-free read compression. *J Comput Biol* 2018;25:825–36.

* Howison M. High-throughput compression of FASTQ data with SeqDB. *IEEE/ACM Trans Comput Biol Bioinform* 2013;10:213–8.

* Jeon YJ, Park SH, Ahn SM *et al.* SOLiDzipper: a high speed encoding method for the next-generation sequencing data. *Evol Bioinform Online* 2011;7:1–6.

* Jones DC, Ruzzo WL, Peng X *et al.* Compression of next-generation sequencing reads aided by highly efficient de novo assembly. *Nucleic Acids Res* 2012;40:e171–e171.

* Kingsford C, Patro R. Reference-based compression of short-read sequences using path encoding. *Bioinformatics* 2015;31:1920–8.

* Kokot M, Gudyś A, Li H *et al.* CoLoRd: compressing long reads. *Nat Methods* 2022;19:441–4.

* Kowalski TM, Grabowski S. PgRc: pseudogenome-based read compressor. *Bioinformatics* 2020;36:2082–9.

* Kozanitis C, Saunders C, Kruglyak S *et al.* Compressing genomic sequence fragments using SlimGene. In: *Research in Computational Molecular Biology: 14th Annual International Conference, RECOMB 2010, Lisbon, Portugal, April 25–28, 2010. Proceedings* 14 pages, pp.310–324. Berlin, Heidelberg: Springer, 2010.

* Kryukov K, Ueda MT, Nakagawa S *et al.* Nucleotide archival format (NAF) enables efficient lossless reference-free compression of DNA sequences. *Bioinformatics* 2019;35:3826–8.

* Lee D, Song G. FastqCLS: a FASTQ compressor for long-read sequencing via read reordering using a novel scoring model. *Bioinformatics* 2022;38:351–6.

* Li H. Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences. *Bioinformatics* 2016;32:2103–10.

* Liu Y, Li J. Hamming-shifting graph of genomic short reads: efficient construction and its application for compression. *PLoS Comput Biol* 2021;17:e1009229.

* Liu Y, Yu Z, Dinger ME *et al.* Index suffix-prefix overlaps by (w, k)-minimizer to generate long contigs for reads compression. *Bioinformatics* 2019;35:2066–74.
Meng Q, Chandak S, Zhu Y *et al.* Reference-free lossless compression of nanopore sequencing reads using an approximate assembly approach. *Sci Rep* 2023;13:2082.

Mohammed MH, Dutta A, Bose T *et al.* Deliminate—a fast and efficient method for loss-less compression of genomic sequences: sequence analysis. *Bioinformatics* 2012;28:2527–9.

Nicolae M, Pathak S, Rajasekaran S. LFQC: a lossless compression algorithm for FASTQ files. *Bioinformatics* 2015;31:3276–81.

Patro R, Kingsford C. Data-dependent bucketing improves reference-free compression of sequencing reads. *Bioinformatics* 2015;31:2770–7.

Pinho AJ, Pratas D. MFCompress: a compression tool for FASTA and multi-FASTA data. *Bioinformatics* 2014;30:117–8.

Popitsch N, von Haeseler A. NGC: lossless and lossy compression of aligned high-throughput sequencing data. *Nucleic Acids Res* 2013; *41*:e27.

Pratas D, Pinho AJ. An experimental sorting method for improving metagenomic data encoding. In: *2024 Data Compression Conference (DCC), Snowbird, USA*, p.578, 2024.

Roguski Ł, Deorowicz S. DSRC 2—industry-oriented compression of FASTQ files. *Bioinformatics* 2014;30:2213–5.

Roguski Ł, Ochoa I, Hernaez M *et al.* FaStore: a space-saving solution for raw sequencing data. *Bioinformatics* 2018;34:2748–56.

Rozov R, Shamir R, Halperin E. Fast lossless compression via cascading bloom filters. In: *BMC Bioinformatics*. Vol. 15, pp.1–8. 2014.

Sakib MN, Tang J, Zheng WJ *et al.* Improving transmission efficiency of large sequence alignment/map (SAM) files. *PLoS One* 2011; *6:e28251*.

Sanderson ND, Kapel N, Rodger G *et al.* Comparison of r9. 4.1/kit10 and r10/kit12 oxford nanopore flowcells and chemistries in bacterial genome reconstruction. *Microbial Genomics* 2023;9:000910.

Sarkar H, Patro R. Quark enables semi-reference-based compression of RNA-seq data. *Bioinformatics* 2017;33:3380–6.

Sun H, Zheng Y, Xie H *et al.* PMFFRC: a large-scale genomic short reads compression optimizer via memory modeling and redundant clustering. *BMC Bioinformatics* 2023;24:454.

Tang T, Li J. Transformation of FASTA files into feature vectors for unsupervised compression of short reads databases. *J Bioinform Comput Biol* 2021;19:2050048.

Tembe W, Lowey J, Suh E. G-SQZ: compact encoding of genomic sequence and quality data. *Bioinformatics* 2010;26:2192–4.

Vandamme L, Cazaux B, Limasset A. K2R: Tinted de Bruijn graphs implementation for efficient read extraction from sequencing datasets. *Bioinform Adv* 2025;5. https://doi.org/10.1093/bioadv/vbaf111

Wan R, Anh VN, Asai K. Transformations for the compression of FASTQ quality scores of next-generation sequencing data. *Bioinformatics* 2012;28:628–35.

Wang R, Li J, Bai Y *et al.* BdBG: a bucket-based method for compressing genome sequencing data with dynamic de Bruijn graphs. *PeerJ* 2018, 6:e5611.

White WTJ, Hendy MD. Compressing DNA sequence databases with coil. *BMC Bioinformatics* 2008;9:242–15.

Xie S, He X, He S *et al.* CURC: a CUDA-based reference-free read compressor. *Bioinformatics* 2022;38:3294–6.

Xing Y, Li G, Wang Z *et al.* GTZ: a fast compression and cloud transmission tool optimized for FASTQ files. *BMC Bioinformatics* 2017; *18*:549–242.

Yanovsky V. Recoil-an algorithm for compression of extremely large datasets of DNA data. *Algorithms Mol Biol* 2011;6:9.

Zhang Y, Li L, Xiao J *et al.* FQZip: lossless reference-based compression of next generation sequencing data in FASTQ format. In: *Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems-Volume 2*, pp.127–135. Cham: Springer, 2015a.

Zhang Y, Li L, Yang Y *et al.* Light-weight reference-based compression of FASTQ data. *BMC Bioinformatics* 2015b;16:188.