<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. SeqBIM 2024 - Journées annuelles du groupe de travail SeqBIM (Séquences en Bioinformatique, Informatique et Mathématiques), Oct 2024, Rennes, France. pp.1-1. hal-04855866

HAL Id: hal-04855866

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

Submitted on 26 Dec 2024

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.

Public Domain
k-mer matrix compression

Alix Regnier, Pierre Peterlongo

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

The analysis of k-mers matrices, essential in agronomy, health and ecology, poses significant challenges regarding Big Data storage and processing. Recently, the tool kmtricks [1] was proposed for creating such matrices and was later used in the kmindex tool [2], designed for indexing large datasets. This opened the doors to indexing terabytes or even petabytes of genomic data. However, one of the main limitations resides in the size of the created matrices, in the order of several terabytes.

In this work, we propose a block compression method on top of the kmtricks matrices, when used by kmindex for indexing and query purposes. The main objective is to achieve sensible compression ratios with a limited impact on the index creation time and on the query time. This method enables partial and targeted decompression, thus optimizing data processing. The BlockCompressor plugin, integrated to kmindex, slices matrices into fixed-size blocks, compressed individually using the LZMA algorithm. The positions of the blocks are encoded using the Elias-Fano succinct data structure [3,4]. This allows both storage of a large number of positions and efficient random accesses.

To improve the compressibility of matrices, we also exploit an idea inspired by phylogenetic compression [5]. Hence, the impact of reordering matrix columns based on phylogenetic order is studied and used as a means of increasing their compressibility.

Preliminary results show that this reordering significantly improves matrix compressibility.

Finally, the approach we propose reduces the storage space required, with a limited impact on query time, making k-mer matrices more accessible and usable.

[1] Lemane, Téo, et al. "Kmtricks: efficient and flexible construction of bloom filters for large sequencing data collections." Bioinformatics Advances 2.1 (2022): vbac029.

[2] Lemane, Téo, et al. "Indexing and real-time user-friendly queries in terabyte-sized complex genomic datasets with kmindex and ORA." Nature Computational Science 4.2 (2024): 104-109.

[3] Fano, Robert Mario. "On the number of bits required to implement an associative memory." Massachusetts Institute of Technology, Project MAC, 1971.

[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, Karel, et al. "Efficient and Robust Search of Microbial Genomes via Phylogenetic Compression." bioRxiv (2023): 2023-04.