Algorithmique pour la détection de variants structuraux dans les graphes de pangénomes – Université de Montpellier

Description

Que ce soit en médecine, écologie, évolution, bioinformatique ou mêmes 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. 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 se présentent sous la forme de textes, généralement sur l’alphabet {A,C,G,T,N}. La baisse des coûts de séquençage et l’amélioration des techniques permet aujourd’hui le séquençage de plusieurs individus d’une même espèce. Pour pouvoir étudier l’ensemble des génomes d’une même espèce, ils sont amalgamés dans une structure dite graphe de variation ou graphe de pangénome ayant pour objectif de factoriser les parties communes. Les individus diffèrent par des variations ponctuelles (de type SNPs) qui peuvent être détectées sans avoir besoin de séquencer complètement l’individu et des variations structurales, comme les inversions ou les duplications, qui impacte une plus grande portion du génomes, et sont difficilement détectable sans le génome complet. L’exploration de cette structure de pangénome et la recherche de variations structurales va donc permettre d’accéder à la variabilité intra-spécifique et de répondre à des questions scientifiques restées jusque là peu explorées. De nombreux outils de construction de graphes de pangénomes et d’exploration voient le jour mais aucun à ce jour ne fait consensus. Par ailleurs, la majorité sont encore lents et/ou imprécis. Il n’y a pas à l’heure actuelle de définition commune de ce que doit-être un pangénome.
L’objectif de cette thèse est dans un premier temps de spécifier formellement la structure de graphe de pangénome que nous souhaitons et les variations structurales que l’on peut y modéliser. Il faudra ensuite mettre au point des algorithmes performant pour construire ces graphes de pangénomes et y rechercher les variations. 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. C’est une espèce de champignon pathogène dont la taille de génome est de l’ordre de 40Mb 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 espace mémoire et temps de calcul sont nécessaires. À terme, tous les outils utilisés en routine dans les analyses bioinformatiques sur les génomes de référence linéaire (l’alignement en particulier) devront pouvoir prendre en entrée des pangénomes de type graphe, cela ouvre de beaux challenges algorithmiques en perspectives.

Compétences requises

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 requise.

Bibliographie

[1] Joel Armstrong et al. ‘Progressive Cactus is a multiple-genome aligner for the thousand-genome era’. In : Nature 587.7833 (nov. 2020). Number : 7833 Publisher : Nature Publishing Group, p. 246-251. issn : 1476-4687. doi : 10 . 1038 / s41586 – 020 – 2871 – y.
[2] Erik Garrison et al. Building pangenome graphs. Pages : 2023.04.05.535718 Section : New Results. 6 avr. 2023. doi : 10.1101/2023.04.05.535718
[3] GitHub – GFA-spec/GFA-spec : Graphical Fragment Assembly (GFA) Format Specification. url : https://github.com/GFA-spec/GFA-spec
[4] Glenn Hickey et al. ‘Pangenome graph construction from genome alignments with Minigraph-Cactus’. In : Nature Biotechnology (10 mai 2023). Publisher : Nature Publishing Group, p. 1-11. issn : 1546-1696. doi : 10.1038/s41587- 023- 01793- w.
[5] New strategies to improve minimap2 alignment accuracy. In : Bioinformatics 37.23 (7 déc. 2021), p. 4572-4574. issn : 1367-4803. doi : 10.1093/bioinformatics/btab705.
[6] The Computational Pan-Genomics Consortium. Computational pan-genomics: status, promises and challenges. Brief Bioinform. 1 janv 2018;19(1):118‐35.
[7] Zekic, T., Holley, G., Stoye, J. (2018). Pan-Genome Storage and Analysis Techniques. In: Setubal, J., Stoye, J., Stadler, P. (eds) Comparative Genomics. Methods in Molecular Biology, vol 1704. Humana Press, New York, NY. https://doi.org/10.1007/978-1-4939-7463-4_2
[8] Heng Li, Xiaowen Feng et Chong Chu. ‘The design and construction of reference pangenome graphs with minigraph’. In : Genome Biology 21.1 (déc. 2020). Number : 1 Publisher : BioMed Central, p. 1-19. issn : 1474-760X. doi : 10 . 1186 / s13059 – 020 – 02168 – z.
[9] Benedict Paten et al. ‘Cactus : Algorithms for genome multiple sequence alignment’. In : Genome Research 21.9 (sept. 2011), p. 1512-1528. issn : 1088-9051. doi : 10.1101/gr.123356.111.

Mots clés

Algorithmique, Graphes, Bioinformatique, Pangénome, Optimisation