Vous êtes ici

Assemblage d’espèces complexes ou de métagénomes par intégration de données de séquençage hétérogènes.

Equipe et encadrants
Département / Equipe: 
Site Web Equipe: 
https://team.inria.fr/genscale/
Directeur de thèse
Pierre Peterlongo
Co-directeur(s), co-encadrant(s)
Jean-François Flot
Contact(s)
NomAdresse e-mailTéléphone
Pierre Peterlongo
pierre.peterlongo@inria.fr
0299847459
Sujet de thèse
Descriptif
Malgrès les développements technologiques récents, l'accès aux séquences des chromosomes des êtres vivant n'est toujours pas résolu. Ce projet de thèse a pour ambition de prendre parti des caractéristiques complémentaires des technologies de séquençage, tout en s'affranchissant de leurs biais respectifs. Dans un contexte 'big data', ceci implique la mise en place de structures de données efficaces, requêtables et dynamiques pour représenter des graphes de séquences, et implique également la création d'algorithmes de parcours contraints de tels graphes. 
    
Contexte
----------
Le séquençage permet d'accéder à l'information stockée dans les génomes. Les séquenceurs dits "de nouvelle génération" ont démocratisé ces dernières années le séquençage, ouvrant la porte à une finesse de compréhension des mécanismes du vivant jamais atteinte jusqu'alors. Les applications sont majeures tant pour les connaissances fondamentales que dans les domaines de l'écologie, de l'agronomie et de la santé où les impacts sociétaux sont capitaux. Actuellement, le goulot d'étranglement limitant l’avancée de la connaissance provient non plus de la génération de ces données, mais  de leur analyse.
Les séquenceurs ne sont pas capables de lire les séquences entières des génomes. Ils sont capables de lire de petits fragments. Les séquences de ces petits fragments sont appelées deslectures. Ainsi les données générées par un séquençage sont composées de millions, voire de milliards de ces lectures, chacune de taille limitée à quelques centaines ou quelques milliers de caractères en fonction de la technologies utilisée.
  
 L'assemblage de ces lectures consiste à reconstruire la séquence (dans de nombreux cas, le génome) dont elles sont issues. De nombreux algorithmes d'assemblage ont été développés au cours des 25 dernières années. Les assemblages obtenus sont malheureusement imparfaits. Ceci est particulièrement vrai dès qu'il s'agit d'espèces complexes, même le génome humain, de loin le plus étudié de tous n'est toujours pas parfaitement assemblé.  La plupart des assemblages de génomes complexes tels ceux des espèces polyploïdes ou des métagénomes (décrits plus bas) sont aujourd'hui médiocres au point de ne pas être exploitables. 
  
Au sein d'une espèce polyploïde, chaque chromosome est présent en plusieurs copies. Une grande partie des génomes “d’intérêt” sont diploïdes (2 copies de chaque chromosomes) comme l’humain, le maïs, le riz ou polyploïdes, comme le blé qui est hexaploïde. Les assembleurs actuels ne permettent pas la séparation des copies distinctes des chromosomes (appeléeshaplotypes). La reconstruction de ces haplotypes est pourtant fondamentale pour de nombreuses applications : comprendre l’impact des mutations sur la fonction des gènes (en particulier en médecine), inférer l’histoire démographique humaine, détecter des signatures de sélection, ou encore détecter des erreurs dans les génomes de référence.
  
Un métagénome est composé, non pas du génome d'un individu, mais de l'intégralité des génomes d'un milieu complet tel qu'un verre d'eau de mer ou une poignée de terre par exemple. À l'image du projet "Tara océan" ou des études sur le microbiome humain, la métagénomique connait un essor considérable. Elle permet un changement d'échelle car elle offre la possibilité d'étudier le fonctionnement d'un milieu complet plutôt que "simplement" d'un individu ou d'une espèce. D'autre part, la métagénomique permet le séquençage d'espèces non cultivable en laboratoire. Ceci est particulièrement intéressant car ces espèces non cultivables représentent une part substantielle des bactéries ou virus. On estime par exemple c'est le cas de 99.9% des bactéries présentes dans l’eau de mer. 
  
La qualité des assemblages est globalement limitée par les lectures trop courtes. En effet, lorsque que le matériel séquencé contient une répétition plus longue que ces lectures, l'assemblage est théoriquement impossible. Ces répétitions (sur une même molécule, entre chromosomes pour les diploïdes ou polyploïdes, ou entre espèces dans le cas de la métagénomique) sont extrêmement nombreuses dans ce que nous appelons ici les génomes complexes.
  
Ce projet de thèse a pour ambition de lever le verrou de l'assemblage des données de séquençage complexes, en séparant les haplotypes et/ou les espèces séquencés. L’idée phare consiste à combiner les données issues de diverses techniques de séquençage et d’exploiter la complémentarité de leurs caractéristiques. Plus précisément, depuis peu, diverses nouvelles technologies de séquençage produisent des lectures plus longues que celles utilisées précédemment. Dans certains cas il est également possible de connaitre la distance approximative entre paires de lectures ou simplement de savoir que deux lectures proviennent de la même molécule. L'intégration de ce nouveau type d'informations longue distance permettra de résoudre les limitations des assembleurs actuels. Ceci représente un défi important du fait des masses de données à considérer, du fait de la forte hétérogénéité de leur caractéristiques et du fait de leur erreurs respectives. Il ne s'agit pas simplement d'intégrer toutes ces données dans des structures déjà existantes mais plutôt de repenser les algorithmes d'assemblages ainsi que les structures de données associées. 
La réussite d'un tel projet permettrait l'accès aux séquences de génomes et de métagénomes jusqu'alors jamais exploitées.
  
Mise en oeuvre 
-----------------
  
Les algorithmes d'assemblage se basent sur l'organisation des données de séquençage dans des graphes, notamment le graphe de "de Bruijn", et sur la recherche de chemins optimaux dans ceux­-ci. Les séquences issues du parcours de ces chemins sont appelées contigs. Ces contigs sont considérés comme des fragments du génome à reconstruire. La présence de branchements dans le graphe limite la taille des contigs. Dans un graphe sans erreur, ces branchements sont principalement dus au polymorphisme ponctuel dans les données (substitutions, insertions ou délétions) au sein de séquences répétées intra ou inter génomes. Ce polymorphisme génère des structures appelées bulles. Les répétitions peuvent être causées par la présence d’éléments particuliers (séquences répétées), par la polyploïdie, par des zones de génomes similaires entre individus, et, dans le cas de données métagénomiques, par le séquençage simultané d'espèces proches. 
  
À l'heure actuelle, afin de produire des séquences les plus longues possibles, les assembleurs ont pour stratégie d’écraser les bulles dans les graphes d’assemblage. Ainsi, par exemple dans le cas de génomes diploïdes, les variants (différences entre chromosomes homologues) sont perdus. Pour pouvoir proposer des assemblages comportant une séquence par haplotype et reflétant ainsi véritablement le contenu génomique des cellules séquencées, les futurs assembleurs devront obligatoirement gérer les bulles sans les écraser. 
  
En plus des lectures simples ou pairées évoquées plus haut, les technologies de séquençage actuelles permettent l’obtention de lectures pairées à longue distance (appelées parfois mate pairs) , qui peuvent soit être issues de protocoles “classiques”, générant des distances distribuées autour d’une valeur moyenne, ou être obtenues par chromosome conformation capture (3C), avec des distances distribuées selon une loi de puissance. Par ailleurs, une troisième génération de séquenceurs disponibles depuis peu (PacBio, Nanopore) permet d’obtenir des lectures de très grandes tailles (plusieurs de dizaines de milliers de paires de bases). L'intégration de ces données devrait permettre, en théorie, de résoudre la (quasi­)totalité des répétitions. En pratique, cette exploitation nécessite d'intégrer des données hétérogènes (c’est­-à-­dire obtenues par une diversité de méthodes) au graphe d'assemblage et de les utiliser comme système de contraintes pour proposer des chemins traversant correctement les répétitions et les zones polymorphes.
Les difficultés associées à ce projet sont dues à la fois à la masse des données à considérer ainsi qu'au bruit dans ces données. Les solutions algorithmiques que nous proposerons devront permettre de traiter quelques centaines de millions ou milliards de séquences simultanément. Ces séquences comportent des erreurs de séquençage (de environ 1% à 15% en fonction des technologies utilisées). Enfin, les informations des paires de lectures longue distance ne sont elles­ mêmes pas complètement 100% fiables car ces jeux de données sont toujours contaminés par des paires de lectures à faible distance, à des taux pouvant atteindre 30%.
  
En pratique ce projet comporte trois jalons principaux. 1/ L'utilisation de méthodes de correction des données. Ce domaine est déjà largement étudié, il s'agira principalement de choisir, d'appliquer et éventuellement d'adapter des solutions existantes. 2/ La mise en oeuvre de structure de graphe pour représenter efficacement ces données. Cette structure devra être facilement requêtable; devra pouvoir être mise à jour et devra offrir la possibilité de représenter à la fois des relations de chevauchement entre séquences mais aussi des informations longue distance ou simplement de co-existance sur la même molécule. 3/ L'exploitation de l'intégralité des données représentées dans le graphe pour produire les séquences des haplotypes recherchés, sous la contrainte des relations de chevauchements et des relations longues distances connues.
  
Notons que l'équipe d'accueil GenScale dispose d'une expertise solide à la fois théorique et appliquée dans le domaine des structures d'indexation dédiées au type de données qui seront intégrées dans ce projet. En particulier l'équipe a développé la librairie GATB qui servira de pierre angulaire pour le développement des structures prévues au sein de ce travail (point 2/). En outre, l'équipe propose de nouvelles approches pour la résolution de systèmes sous contraintes, en particulier appliquées dans le cadre de la phase finale de l'assemblage de contigs appelée le scaffolding. Cette expertise représente un terreau fertile pour résoudre efficacement le point 3/. 
Bibliographie

Librairie GATB :
Drezen, E., Rizk, G., Chikhi, R., Deltel, C., Lemaitre, C., Peterlongo, P., & Lavenier, D. (2014). GATB: Genome Assembly & Analysis Tool Box. Bioinformatics (Oxford, England), 1–3. http://doi.org/10.1093/bioinformatics/btu406

Scaffolding sous contraintes :
Fran, S., Andonov, R., Djidjev, H., Lavenier, D., Fran, S., Andonov, R., … Djidjev, H. (2016). Global Optimization Methods for Genome Scaffolding. 12th International Workshop on Constraint-Based Methods for Bioinformatics , Sep 2016, Toulouse. 
 
Ajout d'informations au graphe d'assemblage : 
Limasset, A., Cazaux, B., Rivals, E., & Peterlongo, P. (2016). Read mapping on de Bruijn graphs. BMC Bioinformatics, 17(1), 237. http://doi.org/10.1186/s12859-016-1103-9
 
Création optimisée du graphe d'assemblage : 
Chikhi, R., Limasset, A., Jackman, S., Simpson, J. T., & Medvedev, P. (2014). On the representation of de bruijn graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 8394 LNBI, pp. 35–55). http://doi.org/10.1007/978-3-319-05269-4-4
  
Début des travaux: 
Automne 2017
Mots clés: 
Assemblage, metagenomique, polyploidie, haplotypage, de Bruijn, long reads, scaffolding sous contraintes, mapping, validations
Lieu: 
IRISA - Campus universitaire de Beaulieu, Rennes