Mots-Clés

pangénomes, graphes, k-mers, strobemers

Description

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 variétés distinctes d’un plante 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 à ce graphe. 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). 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 ciblée « d’ancrage puis extension » (« seed-and-extend »). L’ancrage vise à identifier des sous-graphes portant une séquence similaire à la requête. Il se fait classiquement via la recherche de correspondances entre k-mer (sous-chaînes de longueur 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. Cette approche implique de la recherche exacte de texte, 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, puis des méthodes de programmation dynamique sont utilisées pour aligner la séquence requête et le chemin sélectionné.

Aujourd’hui, une dizaine d’outils proposant des variations de cette approche et les premiers benchmark évaluant la qualité du mapping sur graphe de pangénome [3] ainsi que des travaux préliminaires d’un précédent stage dans notre équipe [4] 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és sur le graphe. C’est d’autant plus regrettable que les variations portées par le graphe de pangénome sont connues pour leur fort potentiel d’impact sur la structure, la régulation et le fonctionnement des gènes [5].

Le stage se place donc un contexte d’amélioration de la qualité du mapping de génomes divergents sur un graphe de pangénome, et plus particulièrement sur l’amélioration de l’étape d’ancrage sur le graphe, afin d ‘améliorer la sensibilité du mapping de séquences divergentes. Il poursuivra des travaux amorcés en 2025, et qui ont aboutit à un prototype logiciel hybride mêlant l’approche Strobemer (une méthode d’ancrage récente) et le logiciel de mapping sur graphe Graphaligner [6]. Le stagiaire exploitera ce prototype pour réaliser un benchmark étendu cherchant à confirmer si la combinaison Strobemer et mapping sur graphe est une piste de recherche prometteuse. Le stagiaire pourra s’appuyer sur des jeux de données issus de différentes espèces végétales et animales liées à des projets en cours dans l’unité (abricotier, choux, bovins, humain…). En terme de développement le benchmark sera basé sur du développement Python, et le gestionnaire de workflow Snakemake. Si intéressé par le développement C++, le stagiaire pourra également aborder des questions relatives au développement du prototype logiciel.

Au-delà des aspects computationnels, ces travaux s’inscrivent dans la cadre dans l’amorçage d’une collaboration internationale avec K. Shalin (université de Stockholm), l’auteur de la méthode Strobemer. Il sera co-encadrant du stage, laissant ouverte la possibilité d’un échange via un court séjour.

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. Andreace F, Lechat P, Dufresne Y, Chikhi R. Construction and representation of human pangenome graphs. preprint. Bioinformatics; 2023. 4. Bouhamout H, Linard B, Zytnicki M. Benchmarking read mapping on pangenomic variation graphs. 2023. 5. 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. 6. . Rautiainen, M., Marschall, T. GraphAligner: rapid and versatile sequence-to-graph alignment. Genome Biol 21, 253 (2020).

Objectifs du stage :

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

• Étudier la méthode Strobemer, comme méthode d’ancrage k-mer sur le graphe de pangénome

• Évaluer la qualité de l’ancrage sur différents jeux de données

• Implémenter un pipeline Snakemake

Profil de candidat souhaité :

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

• bonne connaissance de python (d’autres langages pourront ê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

• intérêt pour l’international (anglais)

Encadrement :

• Le stage sera encadré par Benjamin Linard (MIAT, INRAE, Toulouse) et Kristoffer Sahlin (Université de Stockholm), spécialisés dans le développement d’algorithmes et logiciels pour l’analyse des données génomiques. Localement, Matthias Zytnicki et Christine Gaspin, membres de l’équipe SaAB seront impliqués dans le projet.

• Selon son attrait pour la recherche et l’avancée dans le sujet, l'étudiant aura une opportunité de se présenter au concours doctoral MITT ou SEVAB en vue de l'obtention d'une bourse de thèse.

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