Thesis of Igor Martayan

Algorithm design and implementation for the scale of sequencing data

The management and analysis of large collections of DNA sequences represents a growing challenge for bioinformatics. Advances in sequencing technologies continue to increase both the volume and diversity of available data: public repositories now hold several petabytes of sequences, yet computational limitations in storage and indexing make this data difficult to exploit fully. How, then, should we design algorithms suited to this scale? This thesis addresses the design and implementation of efficient algorithms for genomic sequence analysis, with an emphasis not only on theoretical efficiency but, crucially, on practical performance. We argue that algorithm design and implementation are inseparable: achieving high throughput in practice requires both to be considered together, with a deep understanding of how modern hardware executes code. The first part focuses on high-performance sequence processing. We show that SIMD vectorization, the ability of modern CPUs to operate on multiple values simultaneously, can dramatically accelerate the core steps of a genomic processing pipeline. We present vectorized methods for sequence parsing, rolling hash computation, and minimizer extraction, and demonstrate their practical application. Together, these form a pipeline that processes genomic data at close to hardware-limited throughput. The second part examines how the choice of data representation for substrings of fixed length, or k‑mers, affects the efficiency of data structures and plays an important role in practical performances. We study the relationship between minimizers and necklaces, and show how these representations naturally group related k‑mers together, enabling cache-friendly data structures. Building on this, we propose different compact representations that support efficient k‑mer counting and set operations on large collections of sequences. The third part considers sparser representations of sequence content. We show that by retaining only a carefully chosen fraction of k‑mers, one can reduce both memory footprint and comparison time without sacrificing the ability to answer similarity queries. Across these three axes, our work shows that significant practical gains come from treating algorithm design and implementation as a single, unified problem rather than two separate concerns.

Jury

Mme Camille MARCHET Chargée de recherche Université de Lille Directrice de thèse, M. Sven RAHMANN Professor Saarland University Rapporteur, M. Alexandru TOMESCU Professor University of Helsinki Rapporteur, M. Eric RIVALS Directeur de recherche Université de Montpellier Examinateur, M. Giulio Ermanno PIBIRI Associate Professor Ca’ Foscari University Examinateur, M. Sylvain SALVATI Professeur des universités Université de Lille Examinateur,

Thesis of the team Bonsai defended on 04/09/2026