Vigemers: on the number of k k -mers sharing the same XOR-based minimizer

Florian Ingels, Antoine Limasset, Camille Marchet, Mikaël Salson · 2026

Read Vigemers: on the number of k k -mers sharing the same XOR-based minimizer by Florian Ingels, Antoine Limasset, Camille Marchet, Mikaël Salson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-03337.txt.

Description

Counting how DNA words share a fingerprint is tackled theoretically by Florian Ingels, together with 3 colleagues, in a study of XOR-based minimizers. Bioinformatics handles short fixed-length words from sequencing by assigning each a minimizer, its smallest sub-word under some order, as a fingerprint for sampling, storage, and partitioning. Lexicographic order is known to produce badly unbalanced partitions, pushing the field toward hash-based random orders in practical tools.

Their family replaces the order key with an XOR against a fixed key, an exponentially large family of hash functions. For each sub-word they count how many full words admit it as minimizer, giving the maximum bucket size under complete partitioning. Combinatorial equations adapted from the lexicographic analysis allow dynamic programming computation in efficient time and space.

Catalog record

CREATORFlorian Ingels, Antoine Limasset, Camille Marchet, Mikaël Salson
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-03337

Browse the full library · About the Tower of Babel