Mots-Clés

pangenomes graphes recherche de motifs annotation fonctionnelle

Description

Stage niveau M2 ou 2A/3A Ingénieur selon profil

Durée : jusqu’à 6 mois, débutant entre janvier et mars 2024.

Sujet : Recherche différentielle de motifs par parcours de graphe : applications en biologie

Un génome est classiquement représenté par une séquence dans l’alphabet {A,T,C,G}. Une population peut être représentée par une collection de séquences dont la taille peut rapidement atteindre la dizaine, voir la centaine de milliards de caractères. Pour de nombreux problèmes de biologie, il est essentiel de pouvoir identifier rapidement une sous-chaîne de caractères dans cette collection. Par exemple , la recherche d’un gène peut se faire via la recherche d’un motif connu et associé au gène. Les éditions de ce motif correspondent à autant de mutations. La recherche de sous-chaînes ou de motifs se fait classiquement par des algorithmes du texte appliqués à la collection de séquences.

Plus récemment, il a été proposé de modéliser une collection de génomes ainsi que ses variations sous la forme d’un graphe orienté et coloré, dit graphe de variation (GV) [1]. La collection de séquences est alignée deux à deux, puis un graphe est construit à partir de cet alignement. Les nœuds sont étiquetés par les sous-chaîne communes à au moins deux séquences et les liens représentent leur contiguïté dans au moins une des séquences de la collection (Figure 1-A). Un ensemble de chemins coloré permet de retrouver la séquence originelle (couleurs, Figure 1-A). Tous les autres chemins combineront des variations de séquence d’au moins deux génomes distincts. Ce modèle permet de représenter et d’intégrer les variations génétiques caractérisant les différents individus d’une même espèce. D’un point de vue computationnel, il présente plusieurs avantages : 1) c’est une compression, les sous-chaînes conservées dans plusieurs séquences sont réduite en un nœud, 2) le graphe code la notion de fréquence de chaque variation dans la population (épaisseur des chemins, Figure 1-A) et 3) l’approche standard consistant à aligner une séquence requête au GV pour identifier les variations d’un nouveau génome est moins baisée. En effet, aligner une séquence requête contre un graphe présente l’avantage de pouvoir directement décrire l’état de toute édition (mutation) par rapport à l’ensemble des séquences intégrées. La pangénomique computationnelle est un sujet de recherche très actif et l’utilisation du modèle GV commence à être discutés comme une alternative viable pour de nombreuses approches standard de bio-informatique préalablement basées sur l’alignement entre séquences [2].

Figure 1. A. Graphe de variation : lesnœuds représentent des les sous-chaînes partagées et les liens indiquent leur contiguïtés. Les chemins colorés représentent des ensembles de séquence (l’épaisseur est proportionnelle à sa taille). Le graphe permet de modéliser l’ensemble des variations qui caractérisent les génomes. B. Exemple d’un motif de 9 positions (colonnes) défini via une matrice PSSM. En-dessous, représentation du motif sous la forme d’un logo. Les colonnes 2 et 3 ont une forte probabilité d’être un caractère A. La colonne 5, dont les valeurs sont faibles, peut admettre n’importe quel caractère, l’entropie tend vers son maxima ( ≈0 bit d’information). C. Illustration simplifiée du graphe de variation, les intersection sont les nœuds, la longueur des lignes est proportionnelle à la longueur de la séquence associée à chaque nœud. Le chemin du génome d’un individu est représenté en vert. On désire parcourir ce graphe, tout en recherchant la présence du motif, incluant les motifs chevauchant plusieurs nœuds.

Le stage s’intéressera à un problème mélangeant parcours dans le graphe de variation de génomes et recherche de motifs associés à des fonctions biologiques. Il est en effet désirable de pouvoir annoter directement le graphe via une recherche de motifs. Le projet s’intéressera à la recherche dans le graphe de motifs probabilistes, décrits sous la forme d’une matrice « PSSM » (en.wikipedia.org/wiki/Position_weight_matrix) (figure 1-B, c). Sur la base de cette matrice, un score peut être calculé pour toute sous-chaîne dont la taille correspond au nombre de colonnes de la matrice. Un score élevé indique une forte probabilité que la coordonnée correspondante de la séquence code pour la fonction biologique associée au motif. A l’inverse, un score faible indique la modification voir la perte de cette fonction. Le stage aura pour objectif de transposer le processus d’évaluation d’annotation fonctionnelle via matrice PSSM au modèle GV. Parce ce graphe est acyclique, un processus de tri topologique permet de l’ordonner et il est possible d’imaginer un analogue de fenêtre glissant le long du graphe (en pratique le long des chromosomes) et dans laquelle chaque chemin peut être évalué sur la base de la matrice PSSM (un exemple d’un chemin en vert est sur la figure 1-C). Le stage aura en particulier pour objectif de trouver un algorithme de parcours efficace n’évaluer que les chemins « bicolores » (mélangeant au plus deux génomes). Ces chemins particuliers sont autant d’hypothèses de séquences qui pourraient résulter du croisement de deux individus. Il est alors possible d’imaginer une approche différentielle identifiant tous les sous-graphes dont les chemins de génomes « réels » (unicolores) et « virtuels » (bicolores) associés à des scores significativement différents. Dit autrement, le stage s’intéressera à établir une méthode d’extraction de connaissance. La sortie de l’algorithme sera l’ensemble des chemins bicolores (et la position de séquence associée) maximisant la différence de score PSSM avec les deux chemins unicolores de mêmes couleurs.

Développer un tel algorithme et l’appliquer en pratique sur un GV n’est cependant pas trivial. Pour simplifier le problème, le stage se focalisera dans un premier temps sur le cas des graphes acycliques. Ensuite, le graphe est très grand (jusqu’à 107 nœuds) et la connectivité du graphe peut être localement élevée (Figure 1-C). En pratique, l’introduction d’heuristiques limitant les parcours sera probablement nécessaire. Le stage aura pour objectif de rechercher des solutions à ces problèmes spécifiques au modèle graphe de variation.

D’un point de vue appliqué, les graphes de variation visent à intégrer un maximum de biodiversité pour une espèce donnée via, par exemple, la sélection des séquences issues d’individus adapté à des écosystèmes variés. Le graphe porte alors intrinsèquement l’information des variations génétiques caractérisant les processus d’adaptation des individus à ces environnements. Les algorithmes développés durant le stage seront implémentés et testés sur des graphes jouets construits pour éprouver la méthode, puis sur des graphes de variations construits à partir de génomes animaux et végétaux. Ses résultats participeront à la mise en évidence de croisements in silico intéressants d’un point de vue agronomique (variation des fonctions de résistance à la sécheresse, à un parasite…). L’ensemble des ces travaux s’inscrit donc dans un but de recherche finalisée : l’amélioration des processus de croisements entre espèces cultivées/élevées et sauvages pour l’injection de biodiversité génétique dans nos cultures et élevages. Ce processus est un des piliers de la transition de l’agriculture conventionnelle vers l’agroécologie.

REFERENCES : [1] Hickey, G et al. Pangenome graph construction from genome alignments with Minigraph-Cactus. Nat Biotechnol, 2023. doi.org/10.1038/s41587-023-01793-w. [2] Shuo Wang and others, Graph-based pan-genomes: increased opportunities in plant genomics, Journal of Experimental Botany, Volume 74, Issue 1, 1 January 2023, Pages 24–39, https://doi.org/10.1093/jxb/erac412

Objectifs du stage :

• Acquérir les notions liées au modèle graphe de variation et à la recherche de motif probabilistes (matrices PSSM)

• Développer un algorithme efficace permettant de parcourir le sous-ensemble des chemins bicolores dans un analogue de fenêtre glissante

• L’étendre pour simultanément évaluer à partir d’un motif (PSSM) le score associé à la séquence

• Reporter les chemins et de séquence pour lesquels un score significativement différent est observé entre génome réel et virtuels (les hypothèses de croisement)

Profil de candidat souhaité :

• connaissances en théorie des graphes

• programmation python, C ou C++ (d’autres langages peuvent être considérés)

• intérêt pour les contextes multidisciplinaires et appliqués

• notions d’algorithmes du texte non obligatoires, mais appréciées

• autonomie et capacité de travail en équipe

• capacité de rédaction, de synthèse

Encadrement :

• Le stage sera encadré par Benjamin Linard, spécialisé dans le développement d’algorithmes et logiciels pour l’analyse des données génomiques, et Simon De Givry, spécialisé en théorie des graphes et optimisation sous contraintes.

• Le stagiaire sera hébergé au sein de l’équipe SaAB, unité MIAT, de l’INRAE INRAE Occitanie-Toulouse. (24, Chemin de Borde Rouge 31320 Auzeville-Tolosane).