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

HAL
open science

k-mer matrix compression

Alix Regnier, Pierre Peterlongo

► To cite this version:

Alix Regnier, Pierre Peterlongo. k-mer matrix compression. DSB 2025 - Workshop Data Structures in Bioinformatics, Nadia Pisanti, Mar 2025, Pise, Italy. hal-05448857

HAL Id: hal-05448857

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

Submitted on 8 Jan 2026

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 CC BY 4.0 - Attribution - International License
k-mer matrix compression

Alix Regnier, Pierre Peterlongo

Univ. Rennes, Inria, CNRS, IRISA - UMR 6074, Rennes, F-350

Efficient querying of petabyte-scale genomic data is transformative for advancing research in medicine, ecology, and agronomy. The recent `kmindex` [1] approach, applied to a full snapshot of the Sequence Read Archive (SRA), enabled the development of `logan-search.org`, a powerful search engine. However, the index's substantial size—approximately one petabyte—poses significant maintenance and usability challenges.

The index consists of binary matrices where rows represent datasets, columns represent k-mers (or their hash values), and cell values indicate k-mer presence (0 or 1). In this work we propose a practical way to compress this set of data, splitting matrices into blocks, compressing each block separately using LZMA, and encoding the starting position of blocks using the Elias-Fano succinct data structure [3,4]. The main objective is to achieve sensible compression ratios with a limited impact on the index creation time and on the query time. The approach we propose reduces the storage space required, with a limited impact on query time, making k-mer matrices more accessible and usable.

In addition to this practical solution we explore the idea of using phylogenomic compression [5] techniques by clustering columns corresponding to similar species or datasets. The objective is to increase the compression rate of reordered matrices. We will propose an efficient way to perform this task by reusing the matrix representation itself. We will discuss some ways to determine matrix compressibility and evaluate the potential compression benefits. This metric can be used to determine whether or not indexes need to be compressed, depending on the type of data they represent. We will show preliminary results from these ideas.

## References

[1] Lemane, T., Lezzoche, N., Lecubin, J., Pelletier, E., Lescot, M., Chikhi, R., & Peterlongo, P. (2024). Indexing and real-time user-friendly queries in terabyte-sized complex genomic datasets with `kmindex` and `ORA`. _Nature Computational Science_, _4_(2), 104-109.

[2] Wheeler, D. L., Barrett, T., Benson, D. A., Bryant, S. H., Canese, K., Chetvernin, V., ... & Yaschenko, E. (2007). Database resources of the national center for biotechnology information. _Nucleic acids research_, _36_(suppl 1), D13-D21.

[3] Fano, R. M. (1971). _On the number of bits required to implement an associative memory_. Massachusetts Institute of Technology, Project MAC.

[4] Elias, Peter. Efficient storage and retrieval by content and address of static files. Journal of the ACM (JACM) 21.2 (1974): 246-260.

[5] Břinda, K., Lima, L., Pignotti, S., Quinones-Olvera, N., Salikhov, K., Chikhi, R., ... & Baym, M. (2024). Efficient and robust search of microbial genomes via phylogenetic compression. bioRxiv, 2023-04.