# Rapid searches across million-genome bacterial collections on laptops: a practical methodology for point-of-care applications using k-mers

Francesca Brunetti, Karel Brinda

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

## ► To cite this version:

Francesca Brunetti, Karel Brinda. Rapid searches across million-genome bacterial collections on laptops: a practical methodology for point-of-care applications using k-mers. SIM 2025 - 53rd National Congress of the Italian Society of Microbiology, Sep 2025, Catania, Italy. hal-05446703

HAL Id: hal-05446703

https://inria.hal.science/hal-05446703v1

Submitted on 7 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
# Rapid searches across million-genome bacterial collections on laptops: a practical methodology for point-of-care applications using *k*-mers

FRANCESCA BRUNETTI¹, KAREL BŘINDA²

¹ Department of Public Health and Infectious Diseases, Sapienza University of Rome, Rome, Italy; ²Inria, Irisa, University of Rennes, Rennes, France

**Introduction** - Recent advances in sequencing technologies have led to the generation of massive collections of bacterial genomes, such as 661k (n=661,405) and AllTheBacteria (n=2,440,377), offering great potential for point-of-care (POC) applications, such as in rapid diagnostics and epidemiological surveillance. However, searching across millions of genomes in real-time on portable devices is challenging as existing approaches either search across limited genome subsets (e.g., BLAST), require computational clusters (e.g., BIGSI) or have prohibitive space and time requirements for laptops (e.g., LexicMap). Recently, alignments against these large collections have been made possible by Phylign leveraging the phylogenetic compression technique. However, Phylign's suitability for time-critical applications remains limited due to its reliance on COBS index, which is inefficient when searching divergent or long sequences, like plasmids. Although more modern *k*-mer indexes can be combined with phylogenetic compression, no established methodology exists to guide their selection, application, and parametrization. Therefore, the aim of this study is to define a methodology for *k*-mer-based searches across million-genome collections on standard laptops using phylogenetic compression, to address specific biological questions.

**Materials and Methods** - Our methodology guides the use of *k*-mer searches in 3 steps, as follows. 1) An initial biological question of interest is translated into a *k*-mer-based algorithm, 2) formalizing *k*-mer searches as a combination of 3 elements: query type, reference collection type, and matching mode. 3) This combination guides the selection of *k*-mer indexes to evaluate based on their indexing and searching performance, in order to identify the most suitable one for the given application. The whole methodology was applied to the problem of plasmid search using Phylign and the 661k collection, comparing 4 modern *k*-mer indexes (COBS, Fulgor, Themisto and Metagraph).

**Results** - Different compression power and search speed characteristics were shown by the evaluated indexes. Metagraph offered the best compression power but the slowest plasmid searches. Themisto showed better performance on closely-related genomes. Fulgor offered the best trade-off, having similar index size to Metagraph and COBS while archiving the fastest plasmid searches. As a result, Phylign achieved ~4x faster plasmid searches when combined with Fulgor.

**Discussion and Conclusions** - Rapid searches across million-genome collections are crucial at POC. Our work provided the first practical guidelines for microbiologists to address their biological questions on a large-scale and on standard laptops using *k*-mer searches, paving the way for novel strategies at POC.