Université de Rennes Dynamic Pan-genome graphs Graphes dynamiques de pangénome Structures de donnéesgraphe de de Bruijnindexationk-mèresgénomes Data structuresde Bruijn graphindexingk-mersgenomes Structures de données (informatique) Graphes de de Bruijn Génomique Les progrès rapides des technologies de séquençage ont révolutionné la génomique, conduisant à des bases de données génomiques massives et à des milliers de génomes assemblés. Cette croissance exponentielle des données a mis en évidence les limites des modèles traditionnels basés sur des références et a motivé le développement de représentations pan-génomiques qui reflètent la diversité des espèces. Parmi ces représentations, les graphes de de Bruijn compactés (cDBG) constituent une approche de pointe pour le stockage et les requêtes sur les grands ensembles de données génomiques. En regroupant les séquences redondantes et en représentant efficacement les chevauchements des k-mères, les cDBG minimisent la mémoire et le coût de calcul. Cependant, l'ajout de nouveaux génomes sur le cDBG pose des problèmes en raison de la nature statique de la plupart structures de données basées sur des cDBG, qui nécessitent souvent une reconstruction complète, ce qui les rend coûteux et inefficaces. Pour relever le défi de l'ajout de séquences, des méthodes permettant des mises à jour dynamiques des cDBG sans reconstruction complète sont nécessaires. Cette thèse présente, Cdbgtricks, une méthode de mise à jour d'un cDBG et de son index en ciblant les régions du graphe qui doivent être modifiées. En utilisant l'index mis à jour, Cdbgtricks permet de requêter une séquence et de rapporter les positions de ses k-mères dans le graphe, avec la possibilité de requêter des millions de séquences. The rapid advancements in sequencing technologies have revolutionized genomics, leading to massive genomic databases and thousands of assembled genomes. This exponential growth of data exposed the limitations of traditional reference-based models and motivated the development of pan-genomic representations that reflect species diversity. Among these, compacted de Bruijn graphs (cDBGs) are a cutting-edge approach for storing and querying large genomic datasets. By collapsing redundant sequences and efficiently representing k-mer overlaps, cDBGs minimize memory and computational overhead. However, adding new genomes to a cDBG creates challenges due to the static nature of most cDBG data structures, which often require complete reconstruction, making them costly and inefficient. To address the challenge of adding sequences, methods that allow dynamic updates of cDBGs without full reconstruction are needed. This thesis presents, Cdbgtricks, a method for updating a cDBG and its index by targeting the regions in the graph that needs to be updated. Using the updated index, Cdbgtricks enables querying a sequence and reporting the positions of its k-mers in the graph, with the ability to query millions of sequences. Electronic Thesis or DissertationText en application/pdf1 : 2616 Kohttps://ged.univ-rennes1.fr/nuxeo/site/esupversions/046f12e6-165c-4827-8722-1639b95ea781 Hannoush Khodor 1994-01-29 LB 282957901 khodor.hannouche@gmail.com 2024URENS061 http://www.theses.fr/2024URENS061 2024-12-13 Informatique Université de Rennesthesis.degree.grantor_1 26693823X Doctorat non ouiPeterlongoPierreintervenant_112482062XLemaitreClaireintervenant_2132940418PeterlongoPierreintervenant_112482062XUricaruRalucaintervenant_5151193681MarchetCamilleintervenant_6259182958BlinGuillaumeintervenant_3095050523CabocheSégolèneintervenant_4140692819 MATISSEecoleDoctorale_1 267602553 INRIA-RENNES partenaireRecherche_1 133175863 ddc:004 PeterlongoPierreLemaitreClaireBlinGuillaumeCabocheSégolèneUricaruRalucaMarchetCamilleUniversité de RennesMATISSE INRIA-RENNES ASCII PDF 2678790