Note ABES Structures de données efficaces pour l'indexation des séquences de troisième génération Efficient data structure for third generation sequencing indexation Indexation Séquençage de troisième génération Indexation Third generation sequencing Data structures Bioinformatique Saisie des données (informatique) -- Organisation L'émergence de la troisième génération de séquençage (TGS), technologie produisant deslongs reads, a transformé les approches d'analyse des données génomiques. Bien que ces longsreads permettent de surmonter certaines limites associées aux reads courts, notamment la ré-solution des régions répétées, leur assemblage et leur traitement posent encore aujourd'hui denombreux défis. L'analyse de novo sans recours à un génome de référence s'impose dans certainscontextes comme une stratégie particulièrement pertinente dans de nombreux cas, par exemplelorsque aucun génome de référence n'est disponible, dans le cadre de la transcriptomique ou en-core dans le cas d'études métagénomiques où les données proviennent de multiples organismessouvent inconnus à l'image du projet Tara Oceans récoltant des échantillons planctoniques variés.Pour que ces analyses puissent passer à l'échelle et être efficaces, notamment face au volumecroissant des données mais aussi adaptées aux spécificités des longs reads, il est indispensablede s'appuyer sur des structures d'indexation efficaces et adéquates.Cette thèse s'inscrit dans ce contexte, avec pour objectif principal le développement de solu-tions de recherche d'informations qui permettront l'analyse de novo adaptées aux données issuesdu séquençage de troisième génération. Après une étude de l'état de l'art et de l'identificationde leurs limites, nous avons proposé de nouvelles méthodes d'indexation de longs reads, pourpermettre une exploitation efficace de ces séquences : détection de variations, quantification,génotypage ou encore comparaison entre jeux de données.L'apport central de cette thèse est la mise en place de stratégies, permettant l'association de k-mers aux reads auxquels ils appartiennent, capables de passer à l'échelle. Une première solutionmise en place et utilisable est notre implémentation K2R (k-mer to Reads), capable d'indexer desséquençages de grande taille (plus de 100X de génome humain). Ce nouvel outil repose sur unestratégie d'indexation par minimizers, optimisée pour la performance et paramétrable afin des'adapter à de nombreux cas d'utilisation. Nous avons par la suite étudié comment améliorerl'impact mémoire de K2R, grâce à une méthode de réordonnancement de reads et observé quece réordonnancement permettait également d'optimiser la compression de séquençages longsreads.Dans un second temps, nous avons développé des outils complémentaires à K2R. Nous avonsproposé un outil permettant la recherche en streaming de k-mers : K2Rmini. Il adopte une ap-proche inverse à celle de K2R en indexant les requêtes plutôt que le jeu de données. Nous avonségalement exploré un autre type d'index, complémentaire à K2R : ONIKA. ONIKA repose surune représentation des séquences sous forme de sketchs, qui sont des sous-ensembles de k-mers,permettant une empreinte mémoire réduite. À l'image de K2R, chaque élément est associé auxjeux de données dans lesquels il apparaît, ce qui permet d'effectuer des requêtes rapides etefficaces, y compris lors de la comparaison de grands jeux de données. The emergence of third-generation sequencing (TGS), a technology that produces long reads,has transformed genomic data analysis approaches. Although these long reads overcome cer-tain limitations associated with short reads, notably the resolution of repetitive regions, theirassembly and processing still pose many challenges today. De novo analysis, without using areference genome, therefore stands out as a particularly relevant strategy in many cases, for ins-tance, when no reference genome is available, or in metagenomic studies where data originatesfrom multiple, often unknown organisms, such as the Tara Oceans project which collects diverseplanktonic samples. For these analyses to be scalable and efficient, especially given the growingvolume of data and the specific characteristics of long reads, it was essential to create a new,suitable indexing structure.This thesis is situated within this context, with the main objective of developing informationretrieval solutions that enable de novo analysis adapted to data from third-generation sequen-cing. After a review of the state of the art and the identification of its limitations, we proposednew methods for indexing long reads to allow for the efficient use of these sequences : variationdetection, quantification, genotyping, or comparison between datasets.The central contribution of this thesis is the implementation of scalable strategies for asso-ciating k-mers with the reads to which they belong. A first implemented and usable solutionis our K2R (k-mer to Reads) implementation, capable of indexing large-scale sequencing data(over 100X of the human genome). This new tool is based on a minimizer indexing strategy,optimized for performance, configurable, and versatile to adapt to numerous use cases. We sub-sequently studied how to improve K2R's memory footprint through a read reordering methodand observed that it also allowed to optimize the compression of long-read sequencing data.Secondly, we developed tools complementary to K2R. We proposed a tool for streaming k-mer search : K2Rmini. It adopts an inverse approach to K2R by indexing the queries ratherthan the dataset. We also explored another type of index, complementary to K2R : ONIKA.Specializing in dataset comparison, ONIKA is based on representing sequences as sketches,which are subsets of k-mers, allowing for a reduced memory footprint. Like K2R, each elementis associated with the datasets in which it appears, which enables fast and efficient queries, evenwhen comparing many datasets with one another. Electronic Thesis or Dissertation Text fr PDF 9030497 https://pepite-depot.univ-lille.fr/LIBRE/EDMADIS/2025/2025ULILB051.pdf https://theses.fr/2025ULILB051/abes https://theses.hal.science/tel-05628689 https://theses.hal.science/tel-05628689 https://theses.hal.science/tel-05628689 Vandamme Léa Vandamme 1997-11-17 FR 29694114X https://theses.fr/2025ULILB051 2025ULILB051 https://doi.org/10.70675/fdc56a17z6b3fz45e7z80cez4a9088f7d977 2025-12-18 Informatique et applications Université de Lille (2022-....) 259265152 Doctorat Docteur es non oui Limasset Antoine MADS_DIRECTEUR_DE_THESE_1 223503908 Cazaux Bastien MADS_DIRECTEUR_DE_THESE_2 226877523 Kessaci Marie-Eléonore MADS_PRESIDENT_DU_JURY 163953791 Commes Thérèse MADS_MEMBRE_DU_JURY_1 112246419 Lavenier Dominique MADS_RAPPORTEUR_1 06011911X Gautheret Daniel MADS_RAPPORTEUR_2 061782645 École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) MADS_ECOLE_DOCTORALE_1 258621362 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 410272 18388695X Agence nationale de la recherche (France ; 2005-....) MADS_PARTENAIRE_DE_RECHERCHE_2 121892174 ddc:004 Limasset Antoine Cazaux Bastien Kessaci Marie-Eléonore Commes Thérèse Lavenier Dominique Gautheret Daniel École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) Centre de Recherche en Informatique, Signal et Automatique de Lille Agence nationale de la recherche (France ; 2005-....) PDF 9030497