Graphes dynamiques de pangénome

Résumé : 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.

Title: Dynamic Pangenome Graphs
Keywords: Data structures, de Bruijn graph, indexing, k-mers, genomes
Abstract: 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.