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

HAL
open science

# SeqBIM 2025 Abstracts and Proceedings

Géraldine Jean, Claire Lemaitre, Mikaël Salson

► To cite this version:

Géraldine Jean, Claire Lemaitre, Mikaël Salson. SeqBIM 2025 Abstracts and Proceedings. SeqBIM 2025, Nov 2025, Nantes, France. pp.1-30, 2025. hal-05412009

HAL Id: hal-05412009

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

Submitted on 18 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Abstract and Proceedings of

SeqBIM

2025 - 24-25 nov.
Nantes

November 24-25, 2025

Nantes
Keynote Speaker

Nadia Pisanti

(University of Pisa, Italy & Erable Team INRIA, France)

Mapping, Aligning, and Comparisons with ED strings

**Abstract**

The notion of ED string was introduced as a simple alternative to variation and sequence
graphs for representing a pangenome, that is, a collection of genomic sequences to be analysed
jointly or to be used as a reference. It can also be seen as a directed acyclic graph, whose
edges are labeled by strings. We will overview methods for investigating ED strings: on-line
short read mapping, fast alignment with a linear genome, and comparison of two ED strings.
Keynote Speaker

Sebastian Will

(LIX, Ecole Polytechnique, Institut Polytechnique de Paris)

Efficient prediction of pseudoknotted RNA structures and ensembles

Abstract

The most-commonly used methods for RNA secondary structure analysis are still limited to non-crossing, pseudoknot-free structures.

We will discuss recent exact methods that provide practically applicable tools for minimum free-energy and ensemble prediction including pseudoknots. The technique of sparsification enables space-saving prediction in the large class of CCJ pseudoknots. Furthermore, sparsification and hierarchical folding yield highly efficient, interesting variants of pseudoknot prediction that are ready for large scale applications. Finally, tree decomposition-based code generation enables efficient energy minimization and ensemble predictions for given pseudoknot configurations.
Abstract

# Towards a phylo-k-mer meta-index and classifier for phylogenetic placements in a collection of trees

Benjamin Linard¹*, Fabio Pardi²

¹MIAT, Univ. Toulouse, INRAE Centre Occitanie-Toulouse, Auzeville-Tolosane, France

²LIRMM, Univ. Montpellier, CNRS, MOntpellier, France

*Corresponding author: benjamin.linard@inrae.fr

## Abstract

We previously developed the idea of phylo-k-mers, an original approach in which either nucleotide or amino acid k-mers are computed from a sequence model [1]. More precisely, using a Maximum-Likelihood phylogenetic model of ancestral reconstruction, we compute a matrix of posterior probabilities for each sequence position and tree branch. Then, using this matrix, we compute a k-mer and its associated probability of belonging to a tree branch (a phylo-k-mer). These k-mers are then indexed, using the assumption that they "might" be sampled in the future. As such, phylo-k-mers belong to a category of probabilistic (predicted, not "observed") k-mer methods. This should not be confused with methods such as Bloom filters, where only "observed" k-mers are indexed and queried via probabilistic techniques. In practice, we introduce a probability threshold to explore a reasonable fraction of the phylo-k-mer space.

Phylo-k-mer applications can also be seen as a classification problem. K-mers from sampled sequences are compared to the phylo-k-mer index, and tree branches maximizing the accumulation of high probabilities are selected as the class. This should not be confused with classification into a taxonomy (e.g., Kraken-like approaches [2]). First, in our approach, selecting an internal tree branch means that it was the most likely divergence point: all branches in the subtree showed lower probabilities. On the other hand, Kraken-like approaches fall back to a last common ancestor because no precise position in the subtree could be selected with enough confidence. Second, our method provides an estimate of classification uncertainty. These points are essential when high-precision classification of environmental sequences (e.g., metabarcoding or metagenomics) is targeted. For instance, in viral emergence surveillance, large fractions of sampled sequences may originate from non-referenced genomes, but precise evaluation of divergence and uncertainty is essential for diagnostics.

Previously, we applied phylo-k-mer-based classification to the problems of phylogenetic placement [3] and viral genome recombination detection [4]. In both cases, we built alignment-free methods with a sensitivity comparable to alignment-based methods but with up to two orders of magnitude speed-up. However, the approach also showed several limitations. In particular, when analyzing raw metagenomes,
some reads from untargeted clades can randomly match phylo-k-mers of high prob-
ability. Simultaneously, reads from targeted but divergent clades can match many
phylo-k-mers of low probability. This results in the introduction of false positives, e.g.,
classification of sequences unrelated to the index but associated with a score similar
to true positives. A workaround is to filter edge cases with fast local alignment, but
this reduces the advantages of using our alignment-free approach.

Here, we extended our phylo-k-mer classifier to simultaneously take into account
the probability and the collinearity of phylo-k-mer matches as a means to filter
sequences that are actually related to a particular phylo-k-mer index. We implemented
a simple scoring scheme based on entropy and accumulated probabilities. In practice,
we rapidly extended this idea to allow classification into a collection of phylogenies.
First, we build a phylo-k-mer index for each phylogeny. Then, we build a meta-index
of phylo-k-mers selected among these indices. A similar classifier is then used to
evaluate which index should be selected, then classification into the corresponding
tree branches can be computed (Figure 1). This approach appears to be sufficient
even when phylogenies are based on homologous sequences. For instance, it can
successfully distinguish gene trees showing similar domains.

We will present in detail the method developed and introduce preliminary results
related to the classification of protein sequences into a collection of gene families.
We also aim to discuss several aspects that still call for improvement. For instance,
we identified some computational bottlenecks in the current algorithm and tried to
develop a pseudo-entropy score to reduce cache misses.

<figure><img src="image_3.png" /><figcaption>**Figure 1.** To classify a sequence into a collection of phylogenies, our meta-classifier aims to distinguish the correct phylo-k-mer index (green) from the thousands of other index (red banana). Using a phylo-k-mer meta-index, position and probability associated to k-mer matches are used to compute an entropy (Y-axis) and a probabilistic score (X-axis). This combination allows to select the index to load for precise classification in the selected phylogeny.</figcaption></figure>

References

[1] Benjamin Linard, Krister Swenson, and Fabio Pardi. Rapid alignment-free phylogenetic identification of metagenomic sequences. *Bioinformatics*, 35(18):3303–3312, 01 2019.

[2] Derrick E. Wood, Jennifer Lu, and Ben Langmead. Improved metagenomic analysis with kraken 2. *Genome Biology*, 20(1):257, Nov 2019.

[3] Nikolai Romashchenko, Benjamin Linard, Fabio Pardi, and Eric Rivals. Epik: precise and scalable evolutionary placement with informative k-mers. *Bioinformatics*, 39(12):btad692, 11 2023.

[4] Guillaume E Scholz, Benjamin Linard, Nikolai Romashchenko, Eric Rivals, and Fabio Pardi. Rapid screening and detection of inter-type viral recombinants using phylo-k-mers. *Bioinformatics*, 36(22-23):5351–5360, 12 2020.
Abstract

Inverted colored de Bruin Graph for
practical kmer sets storage

Timothé Rouzé¹, ²*, Rayan Chikhi¹, Antoine Limasset³

¹Institut pasteur, Université Paris Cité, Paris 75724, France

²Sorbonne Université, Collège Doctoral, F-75005, Paris, France

²UMR9189 CRISTAL, Univ Lille, CNRS, Centrale F-59000 Lille, France

*Corresponding author: trouze@pasteur.fr

Abstract

k-mers have become a cornerstone of efficient biological sequence analysis [1, 2, 3, 4, 5, 6]. Unitigs [7], which represent sets of overlapping k-mers as contiguous sequences, are a widely used and efficient representation for k-mer sets across many applications. This approach has been so successful that the Logan [8] project now provides access to all accessions of the Sequence Read Archive (SRA) transformed into unitigs. This initiative processed 50 petabases of raw SRA data, resulting in approximately 2.18 petabytes of compressed unitig sequences. Yet Logan unitigs are compressed on a per-accession basis using the `zstd` compressor, leaving on the table significant inter-sample compression gains. For example, millions of human sequencing experiments lead to considerable content overlap as two human genomes are roughly 99.5% similar [9].

We hypothesize that by leveraging this inter-sample redundancy across Logan, orders of magnitude improvements in its compression can be achieved. However one must avoid designing a scheme where large archives must be entirely decompressed to retrieve only a single sample; this would impractical for SRA-scale data. Thus there is a pressing need to develop methods for efficient, direct decompression of targeted subsets from large compressed unitig collections. The tool `agc` [10] pioneered a related functionality, allowing for the targeted retrieval of individual genomes from a compressed collection. However, `agc`'s alignment-based mechanisms, optimized for relatively large genome sequences, do not work on unitigs. Other genome collection compressors such as Miniphy [11] or MBGC [12] lack targeted retrieval, and tools designed to compress raw sequencing data [13] are also unsuitable.

Colored de Brujin graphs (cDBGs) are subject of extensive recent research [14], and are natural candidates for indexing collections of *k*-mers sets. Numerous lightweight techniques, either exact [15, 16, 17, 18] or probabilistic [1, 19, 20] have been proposed for this task. Though not their primary design goal, these indexing tools often achieve compact cDBG representations, making them space-efficient. A key limitation, however, is their optimization for such *k*-mer-to-color queries. Our objective is the inverse: efficiently retrieving all *k*-mers originating from a specific input dataset $s_j$ (or a set of input datasets).

We propose a method and a proof-of-concept implementation, `kloe`, as the first
tool designed specifically to compress and perform targeted decompression of large
sets of unitigs. The core of our method lies in reorganizing the data around colors
rather than k-mer sequences. By assembling k-mers into **monochromatigs**—paths of
nodes that share an identical color vector and then sorting these sequences into "color
buckets" on disk, **kloe** directly maps a color to the specific data blocks containing
all of its associated k-mers. This architecture fundamentally reorients the data
organization to align with the targeted retrieval query, allowing **kloe** to read only
the necessary portions of the archive, bypassing all irrelevant data.

Our experiments show that kloe achieves a compression ratio competitive with
specialized tools like *ggcat* and far superior to general-purpose compressors. Applied
to 256 human unitig samples, kloe achieved a 15x compression ratio, reducing a
664 GB input to a 43 GB compressed file, while enabling selective retrieval of input
files in under 30 minutes. It is orders of magnitude faster than state-of-the-art
techniques, which require full decompression for the same operation. Currently,
our implementation is expensive in RAM. A future objective is to update the
implementation to a disk based partitioning that should allow further scaling.

References

[1] Phelim Bradley, Henk C Den Bakker, Eduardo PC Rocha, Gil McVean, and Zamin Iqbal. Ultrafast search of all deposited bacterial and viral genomic data. *Nature biotechnology*, 37(2):152-159, 2019.

[2] Nicolas L Bray, Harold Pimentel, Páll Melsted, and Lior Pachter. Near-optimal probabilistic rna-seq quantification. *Nature biotechnology*, 34(5):525-527, 2016.

[3] Katharine M Jenike, Lucía Campos-Domínguez, Marilou Boddé, José Cerca, Christina N Hodson, Michael C Schatz, and Kamil S Jaron. k-mer approaches for biodiversity genomics. *Genome research*, 35(2):219-230, 2025.

[4] Brian D Ondov, Todd J Treangen, Páll Melsted, Adam B Mallonee, Nicholas H Bergman, Sergey Koren, and Adam M Phillippy. Mash: fast genome and metagenome distance estimation using minhash. *Genome biology*, 17(1):132, 2016.

[5] Derrick E Wood and Steven L Salzberg. Kraken: ultrafast metagenomic sequence classification using exact alignments. *Genome biology*, 15(3):R46, 2014.

[6] Heng Li. Minimap2: pairwise alignment for nucleotide sequences. *Bioinformatics*, 34(18):3094-3100, 2018.

[7] Rayan Chikhi, Antoine Limasset, Shaun Jackman, Jared T Simpson, and Paul Medvedev. On the representation of de bruijn graphs. In *International conference on Research in computational molecular biology*, pages 35-55. Springer, 2014.

[8] Rayan Chikhi, Brice Raffestin, Anton Korobeynikov, Robert Edgar, and Artem Babaian. Logan: Planetary-scale genome assembly surveys life's diversity. *bioRxiv*, 2024.
[9] Samuel Levy, Granger Sutton, Pauline C Ng, Lars Feuk, Aaron L Halpern, Brian P Walenz, Nelson Axelrod, Jiaqi Huang, Ewen F Kirkness, Gennady Denisov, et al. The diploid genome sequence of an individual human. *PLoS biology*, 5(10):e254, 2007.

[10] Sebastian Deorowicz, Agnieszka Danek, and Heng Li. Agc: compact representation of assembled genomes with fast queries and updates. *Bioinformatics*, 39(3):btad097, 2023.

[11] Karel Břinda, Leandro Lima, Simone Pignotti, Natalia Quinones-Olvera, Kamil Salikhov, Rayan Chikhi, Gregory Kucherov, Zamin Iqbal, and Michael Baym. Efficient and robust search of microbial genomes via phylogenetic compression. *bioRxiv*, 2024.

[12] Szymon Grabowski and Tomasz M Kowalski. Mbgc: multiple bacteria genome compressor. *GigaScience*, 11:giab099, 2022.

[13] Mathilde Girard, Léa Vandamme, Bastien Cazaux, and Antoine Limasset. OReO: Optimizing Read Order for practical compression. *Bioinformatics Advances*, jun 2025.

[14] Camille Marchet, Christina Boucher, Simon J Puglisi, Paul Medvedev, Mikaël Salson, and Rayan Chikhi. Data structures based on k-mers for querying large collections of sequencing data sets. *Genome research*, 31(1):1-12, 2021.

[15] Mikhail Karasikov, Harun Mustafa, Daniel Danciu, Christopher Barber, Marc Zimmermann, Gunnar Rätsch, and André Kahles. Metagraph: Indexing and analysing nucleotide archives at petabase-scale. *BioRxiv*, pages 2020-10, 2020.

[16] Andrea Cracco and Alexandru I Tomescu. Extremely fast construction and querying of compacted and colored de bruijn graphs with ggcat. *Genome Research*, pages gr-277615, 2023.

[17] Jason Fan, Noor Pratap Singh, Jamshed Khan, Giulio Ermanno Pibiri, and Rob Patro. Fulgor: A fast and compact k-mer index for large-scale matching and color queries. *bioRxiv*, pages 2023-05, 2023.

[18] Jarno N Alanko, Jaakko Vuohtoniemi, Tommi Mäklin, and Simon J Puglisi. Themisto: a scalable colored k-mer index for sensitive pseudoalignment against hundreds of thousands of bacterial genomes. *bioRxiv*, pages 2023-02, 2023.

[19] Camille Marchet and Antoine Limasset. Scalable sequence database search using partitioned aggregated bloom comb trees. *Bioinformatics*, 39(Supplement_1):i252-i259, 2023.

[20] Robert S Harris and Paul Medvedev. Improved representation of sequence bloom trees. *Bioinformatics*, 36(3):721-727, 2020.
# Cartesian Forest Matching *

Bastien Auvray<sup>1,3*</sup>, Julien David<sup>2,3</sup>, Richard Groult<sup>1,3</sup>, Thierry Lecroq<sup>1,3</sup>

**Abstract**

We introduce the notion of Cartesian Forests, which generalizes Cartesian Trees, in order to better deal with partially ordered sequences. We show that algorithms that solve both exact and approximate Cartesian Tree Matching can be adapted to solve Cartesian Forest Matching in linear time in the worst-case for exact matching and linear time on average for approximate matching. We also show a one-to-one correspondence between Cartesian Forests and other combinatorial objects such as Schröder Trees or Parentheses Words.

**Keywords**

Cartesian Tree — Cartesian Forest — Pattern Matching

Cartesian Trees were introduced by Vuillemin in [2]. Given a sequence $x$ of length $m$, its *Cartesian Tree C(x)*, is the binary tree recursively defined as follows:

* if $x$ is empty, then $C(x)$ is the empty tree;

* if $x[1...m]$ is not empty and $x[i]$ is the smallest value of $x$, $C(x)$ is the binary tree with $i$ as its root, the Cartesian Tree of $x[1...i-1]$ as the left subtree and the Cartesian Tree of $x[i+1...m]$ as the right subtree.

In 2019, Park *et al.* [3] proposed a new method of generalized matching called *Cartesian Tree Matching* where one needs to find all factors of a given text that share the same Cartesian Tree as a given pattern. They solved this problem in linear time for both single and multiple pattern matching thanks to a linear representation of the Cartesian Trees. More recently, an approximate version of the problem where one can consider up to one difference between the factor of the text and the pattern was considered in [4], and solutions were given in quadratic time for the worst-case and linear time on average. When dealing with occurrences of values that are equal, one usually considers the first occurrence of said value to be the smallest. In order to better deal with tiebreakers, we introduce the notion of Cartesian Forest.

Given a sequence $x$ of length $m$, its *Cartesian Forest F(x)*, is recursively defined as follows (see Fig 1 for an example):

* if $x$ is empty, then $F(x)$ is the empty forest;

<footnote n="1"><sup>1</sup>Univ Rouen Normandie, Normandie Université, LITIS UR 4108, Rouen, France</footnote>

<footnote n="2"><sup>2</sup>Univ Caen Normandie, Normandie Université, CNRS, GREYC, Caen, France</footnote>

<footnote n="3"><sup>3</sup>CNRS NormaSTIC FR 3638, Caen, Le Havre, Rouen, France</footnote>

<footnote>*Corresponding author: bastien.auvray@univ-rouen.fr</footnote>

<footnote>*This work is based on [1]</footnote>
* if $x[1...m]$ is not empty, let $(r_1, ..., r_k)$ be the ordered sequence of all the $k$ positions of the smallest value of $x$ and let $r_{k+1} = m + 1$, then $F(x)$ is a forest composed of $k$ trees whose roots are $r_1, ..., r_k$, such that:

- the *left* sub-forest of $r_1$ is the Cartesian Forest $F(x[1...r_1-1])$, and

- for $1 \le i \le k$, the *right* sub-forest of $r_i$ is the Cartesian Forest $F(x[r_i + 1...r_{i+1}-1])$.

<figure><img src="image_4.png" /><figcaption>**Figure 1.** A sequence $x$, its associated Cartesian Tree $C(x)$ (resp. Forest $F(x)$).</figcaption></figure>

We also introduce the notion of *Cartesian Forest Matching*, where one needs to find all factors of a given text sharing the same Cartesian Forest as a given pattern. We show that by adapting the linear representations of Cartesian Trees to Cartesian Forests, one can adapt the existing algorithms for exact and approximate Cartesian Tree Matching to Cartesian Forest Matching in a straightforward manner while retaining the same time and space complexities.

We also show that Cartesian Forests are enumerated by the Schröder numbers (Sequence A001003 on OEIS) and have a one-to-one correspondence with known combinatorial objects, such as Schröder Trees or Parentheses Words.

References

[1] Bastien Auvray, Julien David, Richard Groult, and Thierry Lecroq. Cartesian Forest Matching, 2025. https://arxiv.org/abs/2506.02704.

[2] Jean Vuillemin. A unifying look at data structures. Commun. ACM, 23(4):229-239, 1980.

[3] Sung Park, Amihood Amir, Gad Landau, and Kunsoo Park. Cartesian tree matching and indexing. In CPM, pages 1-14, 2019.

[4] Bastien Auvray, Julien David, Samah Ghazawi, Richard Groult, Gad M. Landau, and Thierry Lecroq. Approximate Cartesian Tree matching with one difference, 2025. https://arxiv.org/abs/2505.09236 Submitted at TCS, Ongoing revision.
Abstract

# Scalable comparison of long sequences
through locally consistent parsing

Igor Martayan¹*, Rob Patro², Camille Marchet¹

¹Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France

²Department of Computer Science, University of Maryland, College Park, MD 20440, USA

*Corresponding author: igor.martayan@univ-lille.fr

## Abstract

**Context.** Recent developments in DNA sequencing technologies have made it possible to generate long reads rapidly and with improved accuracy. This enabled significant algorithmic improvements on essential tasks such as assembly or mapping by taking advantage of the lower divergence of the reads [1, 2]. In particular, one effective approach to speed up the processing of long sequences has been to divide them into locally consistent regions [3, 4, 5] and distribute the computation accordingly [6, 7, 8, 9].

**Contribution.** While most existing methods adopt a different formalism depending on their application, we propose a general framework based on three modular building blocks (each of which can be adapted for different use cases):

1. *Parsing* the sequence into multiple non-overlapping *phrases* by applying a locally consistent selection method (e.g. minimizers, prefix-free parsing...).

2. *Fingerprinting* each phrase (e.g. by computing a hash, lexicographic rank...).

3. *Indexing* the sequence of fingerprints (which is shorter than the original sequence but uses a larger alphabet).

Our contribution is threefold:

1. We adapt this framework to support both exact and approximate comparisons, and propose a new mapping algorithm based on this approach.

2. We illustrate how this technique can index sequences in compressed space while supporting efficient queries using suffixent arrays [10, 11].

3. We propose a highly-optimized implementation of the main building blocks using vectorized and parallel parsing and hashing algorithms [12].

## References

[1] Barış Ekim, Bonnie Berger, and Rayan Chikhi. Minimizer-space de bruijn graphs: Whole-genome assembly of long reads in minutes on a personal computer. *Cell Systems*, 12(10):958–968.e6, 2021.
[2] Bariş Ekim, Kristoffer Sahlin, Paul Medvedev, Bonnie Berger, and Rayan Chikhi. Efficient mapping of accurate long reads in minimizer space with mapquik. *Genome Research*, 33(7):1188–1197, 2023.

[3] Michael Roberts, Wayne Hayes, Brian R. Hunt, Stephen M. Mount, and James A. Yorke. Reducing storage requirements for biological sequence comparison. *Bioinformatics*, 20(18):3363–3369, July 2004.

[4] Saul Schleimer, Daniel S. Wilkerson, and Alex Aiken. Winnowing: local algorithms for document fingerprinting. In *Proceedings of the 2003 ACM SIGMOD international conference on Management of data*, SIGMOD '03, pages 76–85, New York, NY, USA, June 2003. Association for Computing Machinery.

[5] Sühleyman Cenk Sahinalp and Uzi Vishkin. Symmetry breaking for suffix tree construction. In *Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing*, STOC '94, page 300–309, New York, NY, USA, 1994. Association for Computing Machinery.

[6] Christina Boucher, Travis Gagie, Alan Kuhnle, Ben Langmead, Giovanni Manzini, and Taher Mun. Prefix-free parsing for building big bwts. *Algorithms for Molecular Biology*, 14(1):13, 2019.

[7] Aaron Hong, Marco Oliva, Dominik Köppl, Hideo Bannai, Christina Boucher, and Travis Gagie. Pfp-fm: an accelerated fm-index. *Algorithms for Molecular Biology*, 19(1):15, 2024.

[8] Diego Díaz-Domínguez, Travis Gagie, Veronica Guerrini, Ben Langmead, Zsuzsanna Lipták, Giovanni Manzini, Francesco Masillo, and Vikram Shivakumar. Prefix-free parsing for merging big bwts. In *International Symposium on String Processing and Information Retrieval*, pages 54–63. Springer, 2025.

[9] Zsuzsanna Lipták, Simone Lucà, and Francesco Masillo. Measuring genomic data with pfp. *bioRxiv*, 2025.

[10] Davide Cenzato, Lore Depuydt, Travis Gagie, Sung-Hwan Kim, Giovanni Manzini, Francisco Olivares, and Nicola Prezza. Suffixient arrays: a new efficient suffix array compression technique. *arXiv preprint arXiv:2407.18753*, 2024.

[11] Ruben Becker, Davide Cenzato, Travis Gagie, Sung-Hwan Kim, Ragnar Groot Koerkamp, Giovanni Manzini, and Nicola Prezza. Compressing suffix trees by path decompositions. *arXiv preprint arXiv:2506.14734*, 2025.

[12] Ragnar Groot Koerkamp and Igor Martayan. SimdMinimizers: Computing Random Minimizers, fast. In Petra Mutzel and Nicola Prezza, editors, *23rd International Symposium on Experimental Algorithms (SEA 2025)*, volume 338 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 20:1–20:19, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Abstract

# When Many Trees Go to War

Mathias Weller<fnref n="1" />, Norbert Zeh<fnref n="2" />

## Abstract

Traditionally, evolutionary relationships between taxa have been modelled with phylogenetic trees, which are rooted trees whose leaves correspond to present-day taxa and whose internal nodes represent ancestral lineages [6]. However, tree models often fail to capture the full complexity of evolutionary histories, leading to the consideration of “reticulate” evolutionary histories, modelled by DAGs [5, 1, 3]. Herein, nodes with in-degree more than one are called *reticulations*. Such a network is said to *display* a tree if the tree can be embedded in the network in a way that respects its topology [3]. A network displaying a given set of *t* trees on the same set of *n* taxa can easily be constructed if the network is allowed to have (*t* − 1)*n* reticulations. An interesting question then is whether there are sets of trees with little enough common structure to make the trivial network essentially the best possible.

Baroni, Semple, and Steel [2] answered this question in the affirmative for *t* = 2, by showing that there are two *n*-leaf caterpillars requiring *n* − 2 reticulations. Recently, van Iersel, Jones, and Weller [8] proved that even displaying 3 caterpillars without restrictions on the type of network may require (3/2 − o(1))*n* reticulations. Here, we strengthen and generalize their result, showing that, for *t* ∈ o(log *n*), there is a set of *t* trees for which the trivial network is *asymptotically* optimal, even if these trees linear (that is, caterpillars) which are, combinatorially, equivalent to sequences.

**Theorem 1.** For all $t \in o(\sqrt{\log n})$, there is a set $\mathcal{T}$ of $t$ (linear) trees on the leaf set $[n]$ such that every network $N$ that displays the trees in $\mathcal{T}$ has $(t - 1 - o(1))n$ reticulations.

**Theorem 2.** For all $t \in o(\log n)$, there is a set $\mathcal{T}$ of $t$ (linear) trees on the leaf set $[n]$ such that every network $N$ that displays the trees in $\mathcal{T}$ has $(t - 1 - o(t))n$ reticulations.

**Theorem 3.** Let $t = c \log n$, for some constant $c > 0$. Then there is a set $\mathcal{T}$ of $t$ (linear) trees on the leaf set $[n]$ such that every network $N$ that displays the trees in $\mathcal{T}$ has

$$r > \frac{(c \log n - 1)n \log n - O(n \log n)}{(c + 1) \log n + o(\log n)} \in \frac{c}{c + 1 + o(1)} n \log n - O(n)$$

reticulations. In particular, as *c* increases, *r* approaches *n* log *n*.

Our main interest in this question stems from its connection to cluster reduction. Roughly speaking, cluster reduction states that, if all input trees have a node with the same set $Q$ of leaves below it, then there is an optimal network displaying the trees that also has a node that can reach exactly the leaves in $Q$. The implied simplification rule

<footnote n="1">¹LIGM, CNRS, Université Gustave Eiffel, Marne la Vallée, France</footnote>

<footnote n="2">²Faculty of Computer Science, Dalhousie University, Halifax, Canada</footnote>
(split the subtrees induced by Q off all trees and work on both parts independently) has been experimentally verified to be decisive for efficiently computing parsimonious networks displaying two trees [4]. Knowing that cluster reduction is "safe" for two trees, an important open question for generalizing known algorithms, is what happens for more than two trees. Relying on the results presented in this work, van Iersel et al. [7] show that cluster reduction fails for four or more trees. That is, there are *t* trees admitting a common cluster *C* which is not a cluster in any optimal network displaying the trees.

As these results hold even if we require all input trees to be caterpillars, they have implications for sequence analysis and representation.

## References

[1] Eric Bapteste et al. "Prokaryotic evolution and the tree of life are two different things". In: *Biology Direct* 4 (2009), p. 34. DOI: 10.1186/1745-6150-4-34.

[2] Mihaela Baroni, Charles Semple, and Mike Steel. "A framework for representing reticulate evolution". In: *Annals of Combinatorics* 8 (2005), pp. 391–408. DOI: 10.1007/s00026-004-0228-0.

[3] Daniel H. Huson, Regula Rupp, and Celine Scornavacca. *Phylogenetic Networks: Concepts, Algorithms and Applications*. Cambridge, UK: Cambridge University Press, 2010. ISBN: 9780521755962. DOI: 10.1017/CBO9780511974076.

[4] Zhijiang Li and Norbert Zeh. "Computing Maximum Agreement Forests without Cluster Partitioning is Folly". In: *25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria*. Vol. 87. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, 56:1-56:14. DOI: 10.4230/LIPICS.ESA.2017.56.

[5] James Mallet. "Hybridization as an invasion of the genome". In: *Trends in Ecology & Evolution* 20.5 (2005), pp. 229–237. DOI: 10.1016/j.tree.2005.02.010.

[6] Charles Semple and Mike Steel. *Phylogenetics*. Oxford, UK: Oxford University Press, 2003. ISBN: 9780198509424.

[7] Leo van Iersel, Mark Jones, Kaari Landry, Simone Linz, Mathias Weller, Norbert Zeh, and Louxin Zhang. "Cluster Reduction on Multiple Binary Trees". Manuscript in preparation. 2025.

[8] Leo van Iersel, Mark Jones, and Mathias Weller. "When three trees go to war". In: *Peer Community Journal* 4 (2024). article no. e54. DOI: https://doi.org/10.24072/pcjournal.419.
Abstract

# Improved strain-level metagenome assembly for modern long reads

Riccardo Vicedomini<fnref n="1" />,*, Rayan Chikhi<fnref n="2" />

## Abstract

Advances in long-read sequencing technologies from PacBio and Oxford Nanopore Technologies (ONT) have paved the way for the development of methods that significantly improve the quality of metagenome assemblies, particularly with the modern PacBio HiFi and ONT R10.4 technologies. Nevertheless, standard metagenome assemblers [1, 2, 3, 4, 5], while providing high-quality species-level reconstructions, are often unable to distinguish and accurately reconstruct genomes of highly similar bacterial strains (i.e., with > 99% sequence identity). Moreover, several long-read-based methods have been recently proposed to address the challenge of reconstructing bacterial strain genomes (or haplotypes) from metagenomic data [6, 7, 8].

In this work we show that existing metagenome assembly tools either produce highly fragmented assemblies or generate longer contigs at the expense of numerous strain-level misassemblies. We also present Strainberry2, an improved version of Strainberry [6], specifically designed for PacBio HiFi and ONT R10.4 sequencing data, aimed at providing a better balance between contiguity and strain-level accuracy. As is common for strain-separation methods, Strainberry2 takes as input a strain-oblivious metagenome assembly (i.e., a species-level assembly) together with a set of accurate long reads. It produces an augmented assembly that recovers strain diversity – absent in the input assembly – by generating strain-specific sequences. Strainberry2 distinguishes itself from competing methods by introducing an upstream dereplication step and a novel strain-phasing algorithm. The dereplication step is aimed at reducing ambiguous read mappings, which are critical for reliably detecting single-nucleotide and structural variants. The strain-phasing algorithm uses an iterative approach that leverages an implicit variant graph constructed from co-occurring single-nucleotide variants in the reads. At each iteration, candidate bacterial haplotypes are defined, while retaining only those supported by a sufficient number of reads.

We ran Strainberry2 and state-of-the-art standard and strain-aware metagenome assemblers on 64 simulated datasets from [7], covering different sequencing technologies, varying numbers of strains (up to 5), multiple bacterial species, and either uniform or staggered strain abundances. We further ran these tools with real sequencing data on the ZymoBIOMICS Gut Microbiome Standard mock community, which includes five highly similar strains of *Escherichia coli* and for which both PacBio HiFi and ONT R10.4 reads are publicly available. The resulting assemblies

<footnote n="1">¹Univ Rennes, CNRS, Inria, IRISA - UMR 6074, Rennes, France</footnote>

<footnote n="2">²Institut Pasteur, Université Paris Cité, CNRS UMR 3525, Paris, France</footnote>

<footnote>*Corresponding author: riccardo.vicedomini@irisa.fr</footnote>
were evaluated with MetaQUAST [9]. To overcome the limitations of MetaQUAST in assessing assemblies against highly similar reference genomes, we complemented the evaluation with a k-mer-based approach. In particular, we adapted several of the metrics introduced in [10] to the strain-aware context to provide a more fine-grained evaluation of completeness, duplication, and strain-switch errors.

On the 64 simulated datasets, Strainberry2 achieved, on average, comparable or significantly better results across all qualitative metrics (e.g., 2-7× fewer misassemblies according to MetaQUAST and at least 10× fewer k-mer-based strain-switch errors). On the real-data mock community, Strainberry2 showed the same trend, particularly with ONT R10.4 data. With PacBio HiFi reads, Strainberry2 delivered results on par with the state-of-the-art hifiasm-meta, providing slightly higher accuracy across qualitative metrics. While hifiasm-meta reached greater contiguity (4× higher NGA50), this came at the cost of 20% more duplicated sequences, highlighting the more balanced trade-off achieved by Strainberry2.

Strainberry2 is an open-source software, implemented in Rust, and publicly available at https://github.com/rvicedomini/rust-strainberry.

## References

[1] Mikhail Kolmogorov et al. metaFlye: scalable long-read metagenome assembly using repeat graphs. *Nature methods*, 17(11):1103–1110, 2020.

[2] Xiaowen Feng et al. Metagenome assembly of high-fidelity long reads with hifiasm-meta. *Nature methods*, 19(6):671–674, 2022.

[3] Gaëtan Benoit et al. High-quality metagenome assembly from long accurate reads with metaMDBG. *Nature Biotechnology*, 42(9):1378–1383, 2024.

[4] Gaëtan Benoit et al. High-quality metagenome assembly from nanopore reads with nanoMDBG. *bioRxiv*, pages 2025–04, 2025.

[5] Jim Shaw et al. High-resolution metagenome assembly for modern long reads with myloasm. *bioRxiv*, pages 2025–09, 2025.

[6] Riccardo Vicedomini et al. Strainberry: automated strain separation in low-complexity metagenomes using long reads. *Nature Communications*, 12(1):4485, 2021.

[7] Ekaterina Kazantseva et al. Strainy: phasing and assembly of strain haplotypes from long-read metagenome sequencing. *Nature Methods*, 21(11):2034–2043, 2024.

[8] Roland Faure et al. HairSplitter: haplotype assembly from long, noisy reads. *Peer Community Journal*, 4, 2024.

[9] Alla Mikheenko, Vladislav Saveliev, and Alexey Gurevich. MetaQUAST: evaluation of metagenome assemblies. *Bioinformatics*, 32(7):1088–1090, 2016.

[10] Wenjuan Yu et al. Comprehensive assessment of 11 de novo HiFi assemblers on complex eukaryotic genomes and metagenomes. *Genome Research*, 34(2):326–340, 2024.
Abstract

# Investigating pre-assembly clustering of HiFi reads for de novo assembly of complex metagenomes

Nicolas Maurice¹,²*, Claire Lemaitre¹, Clémence Frioux², Riccardo Vicedomini¹

¹Univ Rennes, Inria, CNRS, IRISA - UMR 6074, F-35000 Rennes, France

²Inria, Univ. Bordeaux, INRAE, F-33400 Talence, France

*Corresponding author: nicolas.maurice@inria.fr

## Abstract

Despite advancements in sequencing technologies, metagenome assembly in taxonomically rich ecosystems remains challenging. Due to the abundance of low-coverage species, many regions in the assembly graph either lack coverage, are too complex, or present a combination of both factors. Clustering reads prior to assembly reduces complexity, but also decreases coverage within each cluster. While effective in improving short-read assemblies in proof-of-concept studies [4, 1], it has not been widely adopted. In this work, we investigate whether upstream clustering of PacBio HiFi long reads improves assembly quality. To demonstrate the potential of this approach, we simulated an ideal read clustering by comparing the assembly of individual simulated genomes with that of those same simulated genomes merged within a complex ecosystem containing related species. We found that all genomes were better assembled isolated than within the metagenome.

In this work, we propose and develop an iterative assembly approach that relies on a *priori* read clustering. Assembly is first performed cluster-wise and subsequent iteration aims at rescuing mis-clustered reads and improve assembly. More precisely, reads that fail to align back to the cluster-wise assembly are selected for the next step of assembly, together with other unaligned reads of neighboring clusters. For non-hierarchical clustering, all clusters are considered neighbors, while for hierarchical clustering, the process is repeated for each node of the tree, progressively reducing graph complexity and improving coverage. The approach is versatile and can work with multiple assemblers and clustering algorithms. Alternatively, the iterative process can be skipped and all cluster-wise assemblies can be merged together.

We applied these methods on an 81.2 Gbp soil PacBio HiFi metagenomic dataset [2] considering two clustering approaches: (i) a non-hierarchical coverage-based approach (LRbinner [7]) and (ii) a hierarchical taxonomy-driven approach (based on Kraken2 [8]) along with a flexible abundance filter. For the latter, we used two distinct thresholds (1 000 and 1 000 000 reads minimum per cluster). We then used metaMDBG [3] for the assemblies, including a control single-step assembly, and evaluated the results with Mapler [6] to determine which method recovered the greatest portion of the diversity present in the initial sample. All assemblies
were binned with MetaBAT 2. We matched bins obtained from the two clustering-
based strategies with the MetaMDBG-obtained bins using nucleotide identity with
fastANI [5]. Overall, we compared 3 assembly strategies: clustering-based iterative,
clustering-based and a single-step assembly.

Using LRbinner, we obtained 7 distinct read clusters, while the taxonomy-driven approach yielded 246 and 6 clusters, with the 1K and 1M read thresholds respectively. We observed that 86% of the reads aligned against a single-step metaMDBG assembly, while only 73% for LRbinner, 67% for Kraken2 with the 1K threshold, and 71% for Kraken2 with the 1M threshold. The iterative approach increased this metric by only 1% for LRbinner and 2% for Kraken2. Nonetheless, we identified several metaMDBG bins whose closest match is of higher quality in both clustering-based and iterative approaches, in terms of completeness, contamination, and N50.

Assuming perfect clustering, separating reads by species can improve metagenomic assembly. However, current pre-assembly binning methods result in a significant loss of coverage, and our iterative rescue approach fails at significantly improving those results. Nevertheless, those methods can still improve some of the genomes recovered, and there is room for improvement of both the clustering and iterative processes, by using other clustering or assembly methods, or other iterative read transmission criteria.

References

[1] M. Balvert et al. OGRE: Overlap Graph-based metagenomic Read clustEring.
*Bioinformatics*, 37(7):905–912, May 2021. Publisher: Oxford Academic.

[2] C. Belliardo, N. Maurice, et al. Accurate MAG reconstruction from complex soil microbiome through combined short- and HiFi long-reads metagenomics, Sept. 2025.

[3] G. Benoit et al. Efficient High-Quality Metagenome Assembly from Long Accurate Reads using Minimizer-space de Brujin Graphs. 2023.

[4] A. C. Howe et al. Tackling soil diversity with the assembly of large, complex metagenomes. *Proceedings of the National Academy of Sciences of the United States of America*, 111(13):4904–4909, Apr. 2014. Publisher: National Academy of Sciences.

[5] C. Jain et al. High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries. *Nature Communications*, 9(1):5114, Nov. 2018.

[6] N. Maurice et al. Mapler: Assessing assembly quality in taxonomically rich metagenomes sequenced with HiFi reads. *bioRxiv*, 2025. Publisher: Cold Spring Harbor Laboratory _eprint: https://www.biorxiv.org/content/early/2025/03/13/2025.03.10.641994.full.pdf.

[7] A. Wickramarachchi and Y. Lin. Binning long reads in metagenomics datasets using composition and coverage information. *Algorithms for Molecular Biology*, 17(1):1–15, Dec. 2022. Publisher: BioMed Central Ltd.

[8] D. E. Wood et al. Improved metagenomic analysis with Kraken 2. *Genome Biology*, 20(1):1–13, Nov. 2019. Publisher: BioMed Central Ltd.
Abstract

# Multiminimizers: trading time for space in sampling schemes

Florian Ingels¹, Lucas Robidou¹, Igor Martayan¹, Antoine Limasset¹*

UMR9189 CRISTAL, Univ Lille, CNRS, Centrale, F-59000, Lille, France

*Corresponding author: antoine.limasset@univ-lille.fr

## Abstract

**Context:** k-mers, substrings of a fixed length k, are a cornerstone of modern bioinformatics. The ever-increasing volume of sequencing data necessitates efficient representations of k-mers. Crucially, since k-mers are typically processed from reads in a streaming fashion, such representations must effectively group consecutive, overlapping k-mers. Minimizer schemes provide a powerful method for this task, as they select a small, representative subset of features that efficiently cover a large set of k-mers. In such a scheme, a representative substring of length m < k, called a minimizer, is selected from each k-mer based on a predefined order, often determined by a hash function. This design ensures that consecutive, overlapping k-mers frequently share the same minimizer, inducing a natural clustering. This clustering allows for the construction of super-k-mers, leading to highly compact representations (e.g., down to 6 bits per base) [1]. Moreover, it is fundamental to the design of efficient, partitioned data structures for large-scale k-mer analysis.

The efficiency of a minimizer scheme is quantified by its density: the proportion of all possible m-mers that are selected as minimizers. A lower density implies a smaller set of representatives, leading to reduced footprint and performance. Consequently, considerable research effort has recently focused on designing low-density minimizer schemes [2, 3].

**Contribution:** Our contribution is threefold:

1. We formally prove, under minimal hypothesis, that the density of a scheme can be alternatively defined as

$$d = \frac{1}{\mathbb{E}[\text{gap between two consecutive selected positions}]}. $$

The link between density and the expected gap between consecutive minimizers have been remarked in the literature [4, 5], but, to the best of our knowledge, never explicitly formalized as such, nor proved for any scheme.

2. We propose a simple yet efficient method for reducing the density of an existing minimizer scheme, at the expense of computation time. Basically we use N distinct hash functions, generating N possible next super-k-mers, and we select the one covering the most uncovered bases. This improved scheme converges toward the optimal density.

3. We propose an efficient Rust library to compute such a scheme.
References

[1] Igor Martayan, Lucas Robidou, Yoshihiro Shibuya, and Antoine Limasset. Hyper-k-mers: Efficient streaming k-mers representation. In Sriram Sankararaman, editor, *Research in Computational Molecular Biology*, pages 330–335, Cham, 2025. Springer Nature Switzerland.

[2] Saul Schleimer, Daniel S. Wilkerson, and Alex Aiken. Winnowing: local algorithms for document fingerprinting. In *Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data*, SIGMOD '03, page 76–85, New York, NY, USA, 2003. Association for Computing Machinery.

[3] Ragnar Groot Koerkamp and Giulio Ermanno Pibiri. The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers. In Solon P. Pissis and Wing-Kin Sung, editors, *24th International Workshop on Algorithms in Bioinformatics (WABI 2024)*, volume 312 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 11:1–11:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[4] Saul Schleimer, Daniel S Wilkerson, and Alex Aiken. Winnowing: local algorithms for document fingerprinting. In *Proceedings of the 2003 ACM SIGMOD international conference on Management of data*, pages 76–85, 2003.

[5] Hongyu Zheng, Carl Kingsford, and Guillaume Marçais. Sequence-specific minimizers via polar sets. *Bioinformatics*, 37(Supplement 1):i187–i195, 2021.
Abstract

# REINDEER2: practical abundance index at scale

Yohan Hernandez-Courbevoie¹, Mikaël Salson¹, Chloé Bessière²,³, Haoliang Xue⁴, Daniel Gautheret⁵, Camille Marchet¹*, Antoine Limasset¹*

¹Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France

²IRMB, INSERM U1183, Hopital Saint-Eloi, Universite de Montpellier, Montpellier, France

³CRCT, Inserm, CNRS, Université Toulouse III-Paul Sabatier, Centre de Recherches en Cancérologie de Toulouse, Toulouse, France

⁴Independent researcher

⁵I2BC, Université Paris-Saclay, CNRS, CEA, Gif sur Yvette, France

*Co-last authors and corresponding: camille.marchet@univ-lille.fr, antoine.limasset@univ-lille.fr

## 1. Introduction

The last decade has seen an exponential growth in biological sequencing data, now reaching petabyte scale. These data, mainly stored as raw sequencing data in repositories such as the Sequence Read Archive (SRA) and the European Nucleotide Archive (ENA), represent an important resource for analysis in the fields of genomics, transcriptomics and metagenomics.

Considerable effort has gone into accessing and analyzing this large volume of data and recent methods have evolved towards alignment-free solutions as *k*-mers (substrings of length *k*) approaches [1, 2], enabling faster queries on built indexes.

While many tools have focused on indexing problems enabling presence-absence queries on genomic data, transcriptomics, on the other hand, requires the abundance of transcripts from RNA samples. Abundance storage methods also exploit *k*-mers and this paradigm has proven to facilitate the exploration of RNA isoform diversity in thousands of cancer-related RNA-seq datasets, enabling the discovery of new RNA isoforms and biomarkers e.g. [3].

REINDEER [4], Needle [5], and Metagraph [6] represent the state-of-the-art in this field. While these are effective tools, they struggle to scale up to larger datasets, are too resource-intensive or offer rough approximations of abundance, limiting large-scale experiments or nucleotide-level analysis.

We present REINDEER2 [7] that provides a fast, scalable solution for building and updating an index using an approximate membership query data structure which supports sequence abundance queries.

The source is available at github.com/Yohan-HernandezCourbevoie/REINDEER2.

## 2. Methods

Input to the tool is a set of unitig files associated with abundance information provided by tools like ggcat [8] or bcalm2 [9]. Each file is considered as an independent dataset and is indexed individually. The Logan Project [10] makes most of the samples
present on SRA and ENA accessible as unitigs, sparing users a costly pre-processing
phase.

The main index is structured as a matrix-like superposition of Bloom filters where each Bloom filter is representing a dataset, also called color, and an abundance value. This allows us to take advantage of efficient presence-absence index techniques to create an abundance index. In addition, our index is based on succinct structures that take advantage of the sparse distribution of *k*-mers in the matrix, enabling us to achieve satisfying levels of compression and to reduce the memory footprint. Moreover, we partition the index according to the minimisers which allows parallelization, speeding up both indexing and queries.

Intersections of *k*-mer sets of human RNA samples show that some transcripts - as the housekeeping gene mRNA - are present in all datasets. Our method therefore handles ubiquitous *k*-mers aside, storing them directly in a hash table associated with a vector containing their abundance per color, while the rest are indexed in the previously described Bloom filter-based index.

What makes this structure possible is the relatively low number of possible
abundance values. We introduce a novel quantization method, we have chosen
to propose a logarithmic discretization of abundances modulated according to the
number of values required (granularity), the maximum error percentage accepted
and the maximum abundance values taken into account. As the lowest values of
the logarithmic scale tends to repeat, an identity function is applied to correct the
distribution. As a result, abundance values can be recovered with less than 1%
variation from their original counts, providing reliable quantitative insights.

3. Results

Most of the experiments and state-of-the-art comparisons were carried out on the
CCLE (Cancer Cell Line Encyclopedia) collection [11]. When comparing with
REINDEER, Needle and Metagraph, we observed that REINDEER2 is one or several
order of magnitude faster than its concurrents and memory efficient thanks to its
ability to build several sub-indexes and to merge them afterward. REINDEER2 has
been able to index CCLE in 4 hours using 30 threads and less than 32GB RAM.
In an attempt to test REINDEER2 performances on a larger scale, we indexed a
collection of about 10'000 RNA-seq files from melanoma samples. This collection,
covering a total of 67 billion sequences and 3.02 trillion bases, has successfully been
indexed in 2 days and 10 hours using 64 threads.

To evaluate our tool's accuracy in abundance queries, we compared the results
obtained with REINDEER2 to REINDEER that provides exact abundance queries.
The Pearson correlation were computed on the quantification of 1000 human genes.
We obtain a correlation of 0.9832 when indexing all *k*-mers in the Bloom filter-based
index, while building an index with a special handling of ubiquitous *k*-mers allows to
reach a correlation of 0.9885.

As a non *k*-mer-based reference, we compared to Kallisto [12] which uses pseudo-
mapping and an expectation-maximization algorithm to assign reads to assembled
sequences. Kallisto compared to our index handling ubiquitous *k*-mers showed a
Pearson correlation of 0.7569. Normalization of abundances by transcripts per million
(TPM) in both REINDEER2 and Kallisto resulted in a correlation of 0.9224.
References

[1] Camille Marchet. Advances in colored k-mer sets: essentials for the curious. *arXiv preprint arXiv:2409.05214*, 2024.

[2] Camille Marchet, Christina Boucher, Simon J Puglisi, Paul Medvedev, Mikaël Salson, and Rayan Chikhi. Data structures based on k-mers for querying large collections of sequencing data sets. *Genome research*, 31(1):1–12, 2021.

[3] Chloé Bessière, Ahmed Zamani, Romain Pfeifer, Sandra Dailhau, Camille Marchet, Benoit Guibert, Anthony Boureux, Raïssa Silva Da Silva, Nicolas Gilbert, Thérèse Commes, et al. A strong internal promoter drives massive expression of yeats-domain devoid mllt3 transcripts in hsc and most lethal aml. *Cancer communications* (London, England), 2025.

[4] Camille Marchet, Zamin Iqbal, Daniel Gautherset, Mikaël Salson, and Rayan Chikhi. REINDEER: efficient indexing of k-mer presence and abundance in sequencing datasets. *Bioinformatics*, 36(Supplement 1):i177–i185, 2020.

[5] Mitra Darvish, Enrico Seiler, Svenja Mehringer, René Rahn, and Knut Reinert. Needle: a fast and space-efficient prefilter for estimating the quantification of very large collections of expression experiments. *Bioinformatics*, 38(17):4100–4108, 2022.

[6] Mikhail Karasikov, Harun Mustafa, Daniel Danciu, Marc Zimmermann, Christopher Barber, Gunnar Rätsch, and André Kahles. Indexing All Life’s Known Biological Sequences. *bioRxiv*, 2024.

[7] Yohan Hernandez-Courbevoie, Mikael Salson, Chloe Bessiere, Haoliang Xue, Daniel Gautherset, Camille Marchet, and Antoine Limasset. Reindeer2: Practical abundance index at scale. pages 156–171, 2026.

[8] Andrea Cracco and Alexandru I Tomescu. Extremely fast construction and querying of compacted and colored de bruijn graphs with ggcat. *Genome Research*, 33(7):1198–1207, 2023.

[9] Rayan Chikhi, Antoine Limasset, and Paul Medvedev. Compacting de bruijn graphs from sequencing data quickly and in low memory. *Bioinformatics*, 32(12):i201–i208, 06 2016.

[10] Rayan Chikhi, Brice Raffestin, Anton Korobeynikov, Robert C Edgar, and Artem Babaian. Logan: Planetary-Scale Genome Assembly Surveys Life’s Diversity. *bioRxiv*, pages 2024–07, 2024.

[11] Jordi Barretina, Giordano Caponigro, Nicolas Stransky, Kavitha Venkatesan, Adam A Margolin, Sungjoon Kim, Christopher J Wilson, Joseph Lehár, Gregory V Kryukov, Dmitriy Sonkin, et al. The Cancer Cell Line Encyclopedia enables predictive modelling of anticancer drug sensitivity. *Nature*, 483(7391):603–607, 2012.

[12] Delaney K Sullivan, Kyung Hoi Min, Kristján Eldjárn Hjörleifsson, Laura Luebbert, Guillaume Holley, Lambda Moses, Johan Gustafsson, Nicolas L Bray, Harold Pimentel, A Sina Booeshaghi, et al. kallisto, bustools and kb-python
for quantifying bulk, single-cell and single-nucleus RNA-seq. *Nature Protocols*,
pages 1–21, 2024.
Abstract

Comparing and indexing metagenomes at a large
scale using random projections

Roland Faure¹*, Haoran Wu², Hasin Abrar², David Koslicki², Rayan Chikhi¹, Paul Medvedev²

¹Institut Pasteur

²The Pennsylvania State University

*Corresponding author: roland.faure@pasteur.fr

Abstract

The Logan dataset represents a monumental aggregation of public sequencing data, including 5 million metagenomic samples assembled into contigs and unitigs. While this resource holds immense potential for biological discovery, its sheer scale presents formidable computational challenges for comparison, search, and analysis.

In this work, we present a comprehensive framework for the efficient exploration of
the Logan metagenomic collection. Our approach is built upon the random projection
sketching method, which represents each sample as a fixed-dimensional vector (d=2048).
This representation, already explored in [1], presents extremely interesting properties.
From a biological point of view, these vectors can provide accurate approximations of the
Jaccard index between datasets. From a computational point of view, representing datasets
as vectors enable us to perform vector operations, such as PCA, on the collection of dataset
and take advantage of highly optimized libraries such as Eigen, FAISS or scikit-learn.

We will present two main results. The first is a **High-Performance Similarity Search Browser**. The browser allows users to identify samples with high Jaccard similarity to a query in a matter of seconds. The second is a **Large-Scale Clustering** of the 5 million metagenomic datasets. This clustering provides a global map of Logan's metagenomes, which will hopefully enable the detection of ecological patterns and also offer a powerful basis for completing and correcting the Logan metadata.

References

[1] W. Xu, P-K. Hsu, N. Moshiri, S. Yu, T. Rosing. (2024). HyperGen: Compact and Efficient Genome Sketching using Hyperdimensional Vectors. Bioinformatics. 40. 10.1093/bioinformatics/btae452.
# Algorithms for the enumeration of b-canonical
words

Tristan Dubois<fnref n="1" />*, Eric Rivals²

**Abstract**

The border array is the data structure built during the preprocessing of a word in the Morris-Pratt pattern matching algorithm. It is a key data structure for string algorithms. Several articles have proposed algorithms to recognize a border array, that is to determine if an array of integers is the border array of a word. In 1999, Moore et al. defined the notion of b-equivalence between words of length *n* as follows: two words are b-equivalent if they share the same border array. The relation of b-equivalence is an equivalence relationship. A word is said to be b-canonical if it is the smallest of its b-equivalence class in lexicographic order. We propose a linear space algorithm to enumerate all (distinct) b-canonical words of length *n*; this improves on the algorithm of Moore et al. We also present a parallel version of this algorithm and evaluate its performance compared to the non parallel version.

**Keywords**

enumeration — border array — parallel algorithm – pattern matching – stringology

# 1. Introduction

The notions of *b-canonical* and *p-canonical* words were introduced by Moore et al in 1999 [1] when the authors questions the notion of equality among words of a given length *n*. They intuited that, in certain contexts, distinct words are processed identically, and therefore it may be possible to partition words of length *n* into subsets of equivalent words (for some relationships among words). Then for each subset, they proposed to pick a single *canonical* word that serves as a representative for the whole subset.

First, they investigated the notion of position equivalence a.k.a. *p-equivalence*, where two words are equivalent if they share the same set of position identities. They exhibited an enumeration algorithm to list all *p-canonical* words and formulas to compute their number (which in fact corresponds to the Bell numbers).

Second, they turned their attention to a more complex relationship among words, which relates to a seminal data structure known as border array. The *border array* of a word is an integer array that stores *Failure function* of Morris-Pratt algorithm [2]. Let us recall the notion of border, before defining the border array.

**Definition 1.1** Let *u* and *w* be words over an alphabet Σ. The word *u* is a (non empty) border of *w* if and only if *u* is a proper prefix and a suffix of *w*.

**Example 1.1** The word $u = aba$ is a proper prefix and suffix of $w = abaababa$; so, we say $u$ is a border of $w$.

<footnote n="1">¹LIRMM, Montpellier University, CNRS, Montpellier, France</footnote>

<footnote>*Corresponding author: eric.rivals@lirmm.fr</footnote>
Now we can define the border array of a word $u$ (using classical notation on words). Given a word $u$ of length $n$, $B$ is the border array of $u$ if and only if $B$ is an integer array of length $n$ satisfying: for $i$ in $[0..n-1]$, $B[i] :=$ the length of the longest border of $u[0..i-1]$, where $u[0..i-1]$ denotes the prefix of $u$ of length $i$.

Let us denote by $B_u$ the border array of a word $u$. For properties on borders and border arrays, we refer the reader to [3]. From a border array one can compute the set of periods of the word. Hence, enumeration of border arrays or of b-canonical words is linked with the enumeration of all period sets [4, 5].

Moore et al. introduced the notion of b-equivalence, where two words of $\Sigma^n$ are b-equivalent if they share the same border array.

**Definition 1.2** Let $n$ be an integer satisfying $n > 0$. Let $u$ and $v$ be words of $\Sigma^n$.

* $u$ is b-equivalent to $v$ iff $u, v$ share the same border array, i.e. $B_u = B_v$

* Two words are b-distinct if they are not b-equivalent.

The authors noted that both notions of p-equivalence and b-equivalence define equivalence relationships on $\Sigma^n$. Thus, assuming a natural order on the alphabet $\Sigma$, they define a canonical word for each equivalence class. A word $u$ is *b-canonical* if it is the smallest word in lexicographic order among its b-equivalence class.

**Example 1.2** Examples of b-equivalent, b-distinct and b-canonical words.

1. *aa* is b-equivalent to *bb*, to *cc*, etc.

2. *abb* is b-equivalent to *acc*, *abc*, *acb*, *baa*, *bcc*, *bac*, *bca*

3. *abac* is b-equivalent to *acab*, *babc*, etc

4. *aaba* is b-distinct from *abaa*

Moreover, the words *aa*, *abb*, *abac* and *aaba* are all b-canonical.

Note that other works have explored the recognition and enumeration of border arrays, and their link to string matching automata [6, 7, 8], as well as the enumeration of prefix lists [9] (which are an alternative to border arrays).

## 2. Related works and results

In their work, Moore et al. presented an algorithm to enumerate all b-canonical words of length $n$ and their border arrays. For this, they generate the trie of maximal depth $n$, in which each branch spells out a distinct b-canonical word. At one level of depth $i$ with $0 < i \le n$, the leaves contain all prefixes of length $i$ of b-canonical words of length $n$. These prefixes are b-canonical words of length $i$. The generation occurs level by level, corresponding to longer and longer prefixes, and the memory usage is proportional to the number of b-canonical words, which is exponential in $n$. However, the time complexity is linear in the output size (which is optimal).
Using some properties of b-canonical words and of border arrays, we deduce that the trie
can be generated one branch at a time, and thus exhibit an algorithm that enumerates all b-
canonical words of length *n* in linear space. We term this algorithm the OneBranch algorithm.
The property also allowed us to propose parallel algorithms where several processes explore
different branches of the trie. We explore balanced and unbalanced strategy for parallelisation
and compare their running times with that of OneBranch algorithms.

Acknowledgments

We thank the support by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 956229 (EURECA project) and the funding of INCA for the PRT-K23-053 EpiGlio project.

References

[1] D. Moore, W. F. Smyth, and D. Miller. Counting distinct strings. Algorithmica, 23(1):1–13, January 1999.

[2] J. H. Morris, Jr and V. R. Pratt. A linear pattern-matching algorithm. Report 40, University of California, Berkeley, 1970.

[3] William F. Smyth. *Computating Pattern in Strings*. Pearson - Addison Wesley, 2003.

[4] Eric Rivals. Incremental Computation of the Set of Period Sets. In Rastislav Královič and Věra Kůrková, editors, *SOFSEM 2025: Theory and Practice of Computer Science*, volume 15539 of LNCS, pages 254–268, Cham, 2025. Springer Nature Switzerland. preprint at doi:10.48550/arXiv.2410.12077.

[5] Eric Rivals, Michelle Sweering, and Pengfei Wang. Convergence of the number of period sets in strings. Algorithmica, 87:690–711, February 2025.

[6] Jean-Pierre Duval, Thierry Lecroq, and Arnaud Lefebvre. Border array on bounded alphabet. *Journal of Automata, Languages and Combinatorics*:51–60, 2005.

[7] Jean-Pierre Duval, Thierry Lecroq, and Arnaud Lefebvre. Efficient validation and construction of border arrays and validation of string matching automata. *RAIRO - Theoretical Informatics and Applications*, 43(2):281–297, December 2008.

[8] Widmer Bland, Gregory Kucherov, and W. F. Smyth. *Prefix Table Construction and Conversion*, pages 41–53. Springer Berlin Heidelberg, 2013.

[9] Julien Clément and Laura Giambruno. Representing prefix and border tables: results on enumeration. *Mathematical Structures in Computer Science*, 27(2):257–276, May 2015.
Abstract

Optimized phylogenetic batching of million-
genome collections for reduced storage
requirements and faster data retrieval

Tam Truong¹*, Dominique Lavenier¹, Pierre Peterlongo¹, Karel Břinda¹

¹Univ. Rennes, Inria, CNRS, IRISA - UMR 6074, Rennes, F-35000 France

*Corresponding author: khac-minh-tam.truong@irisa.fr

Abstract

The applicability of modern million-genome bacterial collections depends on their efficient compression, which has become increasingly challenging to their growing size and diversity. The best compression results have recently been achieved via phylogenetic compression [1], a method based on compressing genomes in an order corresponding to their evolutionary history. The method has been implemented in MiniPhy, which follows a two level strategy: it first groups genomes into batches of phylogenetically related genomes of a limited size and diversity, and then reorders each batch according to a local phylogenetic tree using for a low-level compressor such as XZ. MiniPhy currently serves as the core compression technique in AllTheBacteria [2] (n=2,440,377), yielding a 40-fold reduction compared to gzip, the main method used previously.

However, the efficiency of MiniPhy has been limited by its ad hoc heuristics for genome
batching. MiniPhy batches are created heuristically, within individual species, based on
the accession order as a proxy for genome similarity – an assumption that holds reasonably
well when most closely related genomes within a collection were also sequenced at the
same time. While this proxy has sufficed for smaller collections (e.g., 661k [3]), in
million-genome collections such as AllTheBacteria single species may comprise over 600k
genomes, and related genomes are less likely to appear in nearby accessions, which
reduces compression efficiency as collections grow. In addition, the MiniPhy workflow
has been tightly coupled with the XZ compressor, unable to fully benefit from modern
specialized compressors, which offer compression ratios similar to or even better than xz
and additionally provide a much faster compression and decompression.

Here, we present a novel method for phylogenetically informed genome batching based on
an approximate reconstruction of species phylogenies. At its core, the method relies on
phylogenetic inference under instance size constraints, coupled with a sketching-based
nearest-neighbor identification algorithm, which jointly enables to infer approximate
phylogenies capable of accurately co-locating most phylogenically related genomes even
in collections comprising million genomes. We show that, when applied to AllTheBacteria
and excluding rare or unknown species (n=2,282k), the method provides improved
batches more than 40% better compressible with XZ (20% reduction when all genomes
included, n=2,440k). When a calibrated MBGC compressor [4] is used instead of XZ, this
size is reduced only to 15GB (4x reduction; 41.3 GB/2x ratio for the whole collection).
Finally, when combined with an optimized AGC [5], this achieves an 18x improvement
in random-access single-genome retrieval (0.5 sec/genome, compared to 8.9-9.5 sec/genome with xz and with base ACG without phylogenetic compression).

References

[1] K. Břinda et al., “Efficient and robust search of microbial genomes via phylogenetic compression,” Nat. Methods, vol. 22, no. 4, pp. 692–697, Apr. 2025, doi: 10.1038/s41592-025-02625-2.

[2] M. Hunt et al., “AllTheBacteria - all bacterial genomes assembled, available and searchable,” Nov. 2024, bioRxiv. doi: 10.1101/2024.03.08.584059.

[3] G. A. Blackwell et al., “Exploring bacterial diversity via a curated and searchable snapshot of archived DNA sequences,” PLoS Biol., vol. 19, no. 11, p. e3001421, Nov. 2021, doi: 10.1371/journal.pbio.3001421.

[4] S. Grabowski and T. M. Kowalski, “MBGC: Multiple Bacteria Genome Compressor,” Gigascience, vol. 11, p. giab099, Jan. 2022, doi: 10.1093/gigascience/giab099.

[5] S. Deorowicz, A. Danek, and H. Li, “AGC: compact representation of assembled genomes with fast queries and updates,” Bioinformatics, vol. 39, no. 3, p. btad097, Mar. 2023, doi: 10.1093/bioinformatics/btad097.