Algorithmique pour la détection de variants structuraux dans les graphes de pangénomes // Algorithmics for detecting structural variations (SVs) in pangenome graphs

Que ce soit en médecine, en écologie, en évolution, en bioinformatique ou dans d'autres champs disciplinaires s'intéressant à l'étude du vivant, le point de départ est dans de nombreux cas le matériel génétique des espèces étudiées, le génome. Depuis le début des années 2000 et la montée en puissance des technologies de séquençage, de nombreux génomes de référence pour diverses espèces ont été publiés. Ces génomes sont présentés sous la forme de textes, généralement écrits dans l'alphabet {A, C, G, T, N}. La baisse des coûts de séquençage et l'amélioration des techniques permettent aujourd'hui de séquencer plusieurs individus d'une même espèce. Pour pouvoir étudier l'ensemble des génomes d'une même espèce, il est courant de les assembler dans une structure appelée graphe de variation ou graphe de pangénome, qui a pour objectif de factoriser les parties communes. Les individus diffèrent par des variations ponctuelles (de type SNPs) sur un seul caractère de la séquence et des variations structurales, comme les inversions ou les duplications, qui impactent une plus grande portion de la séquence. L'exploration des structures de pangénome pour la recherche de variations structurales (SVs) va donc permettre d'accéder à la variabilité intra-spécifique sur ce type de variations, ce qui était jusqu'ici possible seulement sur les SNPs qui ne nécessitent pas le séquençage complet. Trois outils de construction de graphes de pangénomes sont principalement utilisés : Minigraph, Minigraph-Cactus et PGGB, mais il n'y a pas à l'heure actuelle de définition commune de ce que doit être un pangénome. Cela entraîne des graphes différents produits par ces outils, ce qui ajoute un niveau de difficulté à la recherche de SVs.

L'objectif de cette thèse est, dans un premier temps, de caractériser formellement la structure de graphe de pangénome et les variations structurales que l'on peut y détecter. L'une des hypothèses clés de ce projet est que différents types de SVs génèrent différents patrons topologiques (c'est-à-dire des motifs spécifiques et complexes ressemblant à des bulles). Ces motifs complexes ne peuvent pas être caractérisés avec précision et exactitude par les outils de détection de SNPs, qui cherchent des bulles simples. Dans un deuxième temps, nous voulons mettre au point des algorithmes performants pour rechercher les SVs. Ces algorithmes seront testés à la fois sur des données simulées et des données réelles. Dans l'équipe d'accueil, un jeu de données de 250 individus de Pseudogymnoascus destructans est en cours de séquençage. Il s'agit d'une espèce de champignon pathogène dont le génome est de l'ordre de 40 Mb et qui présente de nombreuses variations structurales entre individus. C'est donc un candidat approprié pour tester nos méthodes.

Par ailleurs, il est important de garder à l'esprit que les données sur lesquelles nous devrons appliquer nos méthodes ne vont cesser de croître et que des algorithmes performants à la fois en termes d'espace mémoire et de temps de calcul sont nécessaires. À terme, tous les outils utilisés en routine dans les analyses bioinformatiques sur les génomes linéaires (en particulier l'alignement) devront pouvoir prendre en entrée des pangénomes de type graphe. Cela ouvre de belles perspectives algorithmiques.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Whether in medicine, ecology, evolution, bioinformatics or any other discipline concerned with the study of living things, the starting point in many cases is the genetic material of the species being studied, the genome. Since the early 2000s and the advent of sequencing technologies, many reference genomes have been published for different species. These genomes are presented in the form of texts, generally written in the alphabet {A, C, G, T, N}. As the cost of sequencing has fallen and techniques have improved, it is now possible to sequence several individuals of the same species. To study all the genomes of the same species, it is common to assemble them in a structure called a variation graph or pangenome graph (PG), which aims to capture the common parts. Individuals differ by single nucleotide polymorphisms (SNPs), which are variations in a single character of the sequence, and structural variations (SVs), such as inversions or duplications, which affect a larger part of the sequence. Exploring pangenome structures for SVs will therefore provide access to intra-specific variability for this type of variation, which was previously only possible for SNPs (which do not require full sequencing). Three main PG construction tools are used: Minigraph, Minigraph-Cactus and PGGB, but there is currently no common definition of what a pangenome should be. This results in different graphs being produced by these tools, adding a level of difficulty to the search for SVs.

The aim of this PhD thesis is, firstly, to formally characterise the structure of the pangenome graph and the structural variations that can be detected there. One of the key assumptions of this project is that different types of SVs generate different topological patterns (i.e. specific and complex bubble-like motifs). These complex patterns cannot be accurately characterised by SNP detection tools that look for simple bubbles. Secondly, we will develop powerful algorithms to search for SVs. These algorithms will be tested on both simulated and real data. The host team is currently sequencing a dataset of 250 individuals of Pseudogymnoascus destructans. This is a pathogenic fungal species with a genome of about 40 Mb, which shows numerous structural variations between individuals. It is therefore a good candidate for testing our methods.

It is also important to bear in mind that the amount of data to which we will need to apply our methods will continue to grow, requiring algorithms that are efficient in terms of both memory and computational time. Eventually, all tools routinely used in bioinformatic analyses of linear genomes (especially alignment) will need to be able to take graph-type pangenomes as input. This opens up great algorithmic perspectives.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2025

Contrat doctoral

Concours pour un contrat doctoral

Université de Montpellier

166 I2S - Information, Structures, Systèmes

Le ou la candidate devra avoir de solides compétences méthodologiques et la volonté d'implémenter ses algorithmes. En particulier, le ou la candidate devra être à l'aise en algorithmique du texte et connaitre la théorie des graphes. Une connaissance des problématiques bioinformatiques liées au séquençage (pour l'obtention des données), à l'alignement de séquences et à l'évolution en général est recommandée.
The candidate must have strong methodological skills and a willingness to implement their algorithms. In particular, the candidate must be comfortable with text algorithms and familiar with graph theory. Knowledge of bioinformatics issues related to sequencing (for obtaining data), sequence alignment, and evolution in general is recommended.