Mots-Clés

pangenomes, graphes, k-mers, mapping, genotypage

Description

Stage niveau M2 ou 3A Ingénieur

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

Sujet : Recherche de k-mers sur graphe de pangénome dans un contexte de requêtes divergentes

Un des grands défis de la biologie est d’établir des liens entre les gènes (génotype) et l’ensemble des caractères apparents d’un individu (phénotype). Par exemple, lorsque deux populations distinctes d’un végétal présentent une variation de résistance à la sécheresse, il est désirable d’identifier les variations génétiques à l’origine de cette différence.

Un génome peut être représenté par une séquence de caractères {A,T,G,C} et la diversité des génomes d’une même espèce peut être modélisé sous la forme d’un graphe de pangénome. Le modèle le plus utilisé dans le contexte des génomes eucaryotes (animaux, plantes) est le graphe de variation [1, 2], un graphe dirigé dont les nœuds sont labellisés par une sous-chaîne de la séquence des génomes et dont les liens indiquent leur contiguïté dans au moins un des génomes (figure 1). Le génome d’un individu est un chemin dans ce graphe. Ce modèle permet avant tout de modéliser les variations génomiques sous la forme de chaînes alternatives appelées « bulles » et associables à des polymorphismes (figure 1).

Figure 1. Graphe de variation : les nœ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 génomes. L’épaisseur est proportionnelle au nombre de génome partageant un nœud. Les chemins alternatifs (« bulles ») montrent que chaque individu porte un génome propre. En pratique, le graphe peut présenter une topologie plus complexe que ce schéma simplifié.

Pour étudier un nouveau génome, il est possible de comparer sa séquence à un graphe de variation intégrant les génomes précédemment connus. Ce processus appelé « mapping » est complexe car avant même de pouvoir comparer la requête à une séquence portée par le graphe, il est nécessaire d’identifier quel chemin dans le graphe porte une séquence similaire à la requête. Cette recherche est rendue difficile par la grande taille du graphe (>108 nœuds, pour 12 bovins [3]), tester tous les chemins possibles n’est tout simplement pas réalisable en pratique. Pour pallier à cette difficulté, le mapping se base sur une approche d’ancrage puis extension (seed-and-extend). L’ancrage se fait via la recherche des correspondances entre k-mer (sous-chaînes de longeur k) de la séquence requête et k-mers préalablement indexés pour les différents nœuds du graphe de pangénome. Elle est généralement basée sur une recherche exacte, n’autorisant aucune édition de séquence. La seconde étape consiste à choisir dans le graphe un chemin maximisant un critère basé sur ces ancres, l’approche la plus commune étant de résoudre le problème de « colinear chaning » [7]. Une fois ce chemin identifié, des méthodes de programmation dynamique classiques sont utilisées pour aligner la séquence associée au chemin sélectionné et la requête.

Aujourd’hui, une dizaine d’outils proposant des variations de cette approche et exploitant différents algorithmes sont disponibles (dont 5 publiés [4]). Les premiers benchmark évaluant la qualité du mapping sur graphe de pangénome [4] ainsi que des travaux préliminaires d’un précédent stage dans notre équipe [5] concordent et indiquent que la qualité du mapping peut rapidement baisser lorsque des séquences issues de génomes divergents (en terme de distance génétique) sont mappées sur le graphe. Ce problème s’amplifie lorsque séquence requête et chemins dans le graphe diffèrent par l’introduction ou la suppression de longs fragments dans le nouveau génome. C’est d’autant plus regrettable que ces variations, pourtant omniprésentes chez les organismes eucaryotes, sont connues pour leur fort potentiel d’impact sur la structure, la régulation et le fonctionnement des gènes [6].

Le stage que nous proposons s’intéressera à évaluer les raisons de cette perte de sensibilité et à poursuivre des travaux de benchmarking et développement logiciel autour des graphes de pangénome. Nous souhaitons en particulier étudier les deux premières étapes du processus de mapping sur graphe de pangénome. Le stage s’intéressera à benchmarker le comportement de la recherche de correspondances k-mers dans le graphe. Le résultat de cette recherche est critique pour que le colinear chaining (2ème étape) dispose de suffisamment d’information pour choisir un chemin dans le graphe. Dans un second temps, le stagiaire pourra proposer des modifications de l’approche et sera amené à développer un prototype logiciel implémentant ses idées. Le prototype sera ensuite être intégré dans le pipeline d’un outil de mapping existant afin de réaliser l’ensemble des étapes et d’évaluer si la sensibilité a été améliorée lorsque sont mappées des séquences requêtes très divergentes des génomes intégrés dans le graphe.

Au-delà des aspects computationnels, l’ensemble des ces travaux s’inscrit également dans un but de recherche finalisée. Notamment l’amélioration des processus de croisements entre espèces cultivées et sauvages, qui visent à augmenter la biodiversité génétique dans nos cultures [8]. Cette approche est un des piliers de la transition de l’agriculture conventionnelle vers l’agroécologie. Pour tester ses développements, le stagiaire pourra s’appuyer sur des jeux de données issus de différentes espèces végétales et animales issues des projets de l’unité.

REFERENCES : 1. Garrison E, Sirén J, Novak AM, Hickey G, Eizenga JM, Dawson ET, et al. Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat Biotechnol. 2018;36:875–9. 2. Garrison E, Guarracino A, Heumos S, Villani F, Bao Z, Tattini L, et al. Building pangenome graphs. preprint. Bioinformatics; 2023. 3. Crysnanto D, Leonard AS, Fang Z-H, Pausch H. Novel functional sequences uncovered through a bovine multiassembly graph. Proc Natl Acad Sci USA. 2021;118:e2101056118. 4. Andreace F, Lechat P, Dufresne Y, Chikhi R. Construction and representation of human pangenome graphs. preprint. Bioinformatics; 2023. 5. Bouhamout H, Linard B, Zytnicki M. Benchmarking read mapping on pangenomic variation graphs. 2023. 6. Wang S, Qian Y-Q, Zhao R-P, Chen L-L, Song J-M. Graph-based pan-genomes: increased opportunities in plant genomics. Journal of Experimental Botany. 2023;74:24–39. 7. Chandra G, Jain C. Sequence to graph alignment using gap-sensitive co-linear chaining. 8. Tay Fernandez CG, Nestor BJ, Danilevicz MF, Gill M, Petereit J, Bayer PE, et al. Pangenomes as a Resource to Accelerate Breeding of Under-Utilised Crop Species. IJMS. 2022;23:2671.

Objectifs du stage :

• Acquérir les notions liées au modèle du graphe de variations et aux méthodes k-mer

• Benchmarker la 1ère étape du mapping, c-à-d la recherche de correspondances k-mer

• Proposer des améliorations de cette recherche pour des séquences requêtes divergentes

• Les implémenter dans un prototype logiciel

• Injecter ce prototype dans un outil de mapping existant, afin de tester la solution proposée

Profil de candidat souhaité :

• connaissances en théorie des graphes non obligatoires mais bienvenues

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

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

• autonomie et capacité de travail en équipe

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

Encadrement :

• Le stage sera encadré par Benjamin Linard et Matthias Zytnicki, spécialisés dans le développement d’algorithmes et logiciels pour l’analyse des données génomiques

• 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).