Technologies de séquençage
Le séquençage de l’ADN a été inventé en 1977, par deux équipes de recherche indépendantes. L’une d’entre elles était menée par Frederick Sanger, à l’université de Cambridge , et l’autre, par Allan Maxam et Walter Gilbert, à l’université de Harvard. Bien qu’ayant eu lieu la même année, ces deux travaux de recherche sont totalement indépendants, et ont permis à Sanger et Gilbert de se voir tous deux attribuer le prix Nobel de chimie en 1980. En effet, cette découverte fut une avancée majeure dans le monde de la biologie, permettant d’étudier la composition ADN de toute vie biologique sur Terre, et ouvrant ainsi la porte à l’étude du code génétique des êtres vivants.
Le séquençage de l’ADN repose sur divers principes biochimiques, et vise à retranscrire l’information relative au génome, contenue dans un échantillon d’ADN, sous forme de chaînes de caractères, sur l’alphabet ADN de 4 lettres. Une cinquième lettre, N, peut toutefois être présente au sein des chaînes caractères produites. Cette lettre dénote alors une ambiguïté rencontrée lors du séquençage, et peut représenter n’importe laquelle des 4 bases. Ces chaînes de caractères, appelées reads, représentent des fragments de la séquence d’ADN de l’individu ou de l’espèce séquencé. De plus, ces reads sont imparfaits, et contiennent des erreurs de séquençage dont les types (substitution, insertion, ou délétion) et les taux (de 0,001 à 30%) varient en fonction des technologies utilisées. En effet, au vu des enjeux du séquençage de l’ADN, les recherches à ce sujet se sont multipliées depuis 1977, et de nombreuses technologies de séquençage ont ainsi été développées.
Les technologies de Sanger et de Maxam-Gilbert se sont cependant longtemps imposées comme les technologies de séquençage les plus utilisées par les biologistes. En particulier, la technologie Sanger, au vu de sa haute efficacité et de sa faible radio-activité, a été plus largement adoptée que la technologie Maxam-Gilbert. Ces découvertes ont cependant grandement inspiré les chercheurs à développer de nouvelles technologies de séquençage, plus rapides, plus efficaces, et moins coûteuses. De ce fait, le séquençage de l’ADN a grandement évolué depuis son introduction, en 1977.
Un historique des technologies de séquençage est ainsi présenté ici, des méthodes de Sanger et Maxam-Gilbert, dites de première génération, aux méthodes les plus récentes, dites de troisième génération.
Correction hybride
La correction hybride fut la première approche de correction à être décrite dans la littérature. Cette stratégie se base sur un ensemble de reads courts et un ensemble de reads longs séquencés pour le même individu. Elle vise à utiliser l’information, plus précise, contenue dans les reads courts, afin d’accroître la qualité des reads longs.
Quatre approches différentes existent actuellement dans le domaine de la correction hybride. L’alignement des reads courts sur les reads longs. Une fois les reads courts alignés, les reads longs peuvent en effet être corrigés, en calculant, pour chacun d’eux, une séquence consensus à partir du sous-ensemble de reads courts associé. PBcR/ PacBioToCA , LSC, Proovread, Nanocorr, NaS, LSCplus , CoLoRMap, et HECIL se basent sur cette approche.
L’alignement des reads longs sur les contigs obtenus par un assemblage des reads courts. De la même façon, les reads longs peuvent être corrigés en fonction des contigs avec lesquels ils s’alignent, en calculant des séquences consensus à partir de ces derniers. ECTools , HALC, et MiRCA adoptent cette méthodologie.
L’utilisation d’un graphe de de Bruijn, construit à partir de l’ensemble des kmers des reads courts. Une fois construit, les reads longs peuvent en effet être y être ancrés. Ce dernier peut alors être traversé, afin de trouver des chemins permettant de relier les régions ancrées des reads longs, et ainsi corriger les régions non ancrées. LoRDEC , Jabba , et FMLRC reposent sur cette stratégie. L’utilisation de modèles de Markov cachés. Ces derniers peuvent en effet être utilisés afin de représenter les reads longs. Les modèles peuvent ensuite être entraînés à l’aide des reads courts, avant d’en extraire des séquences consensus, représentant les reads longs corrigés. Hercules se base sur cette approche.
Auto-correction
L’auto-correction vise à s’affranchir de la nécessité de reads courts complémentaires, et à corriger les reads longs en se basant uniquement sur les informations que contiennent leurs séquences. L’auto-correction se divise en deux principales approches.
L’alignement multiple. Cette approche est similaire aux approches de correction hybride par alignement de reads courts ou de contigs. En effet, une fois alignés entre eux, les reads longs peuvent être corrigés, en calculant, pour chacun d’eux, une séquence consensus à partir du sous-ensemble de reads longs alignés. PBDAGCon (le module de correction de l’assembleur HGAP), PBcR-BLASR, Sprai 3, PBcR-MHAP, Fal-conSense (le module de correction de l’assembleur Falcon) , Sparc , le module de correction intégré dans l’assembleur Canu, MECAT et FLAS reposent sur cette approche.
L’utilisation d’un graphe de de Bruijn. D’une manière similaire à l’approche de correction hybride par graphe de de Bruijn , une fois le graphe construit, les reads longs peuvent en effet y être ancrés. Le graphe peut alors être traversé, afin de trouver des chemins permettant de relier les régions ancrées des reads longs, et ainsi corriger les régions non ancrées. LoRMA et Daccord se basent sur cette approche.
Validation de la stratégie de segmentation
Afin de valider la stratégie de segmentation pour l’alignement multiple, nous étudions dans quelle mesure les résultats obtenus en appliquant cette stratégie diffèrent des résultats obtenus via un alignement multiple classique. Nous comparons donc les résultats produits par ELECTOR, en utilisant la stratégie de segmentation, et en utilisant l’implémentation classique des graphes d’alignement d’ordre partiel.
Afin de valider la stratégie de segmentation, les métriques produites par ces deux approches doivent alors être extrêmement similaires, et un important gain de temps doit être obtenu via l’approche utilisant la stratégie de segmentation.
Trois expériences sont présentées, sur des jeux de données simulées à partir du génome d’E. coli, en faisant varier la longueur des reads, afin d’impacter le temps d’exécution. Les trois jeux de données de ces expériences ont été simulés avec Sim-LoRD, en affectant aux reads un taux d’erreurs de 10%, une profondeur de séquençage de 100x, et des longueurs fixées à 1 000, 10 000 et 100 000 paires de bases. Les reads ont ensuite été corrigés avec le module de correction de Canu, en utilisant les paramètres par défaut, avant de lancer les procédures d’évaluation. Les résultats de ces expériences montrent que les métriques calculées via l’approche utilisant la stratégie de segmentation ne diffèrent que très légèrement des métriques calculées via l’approche d’alignement multiple classique. En revanche, en utilisant la stratégie de segmentation, un gain de temps considérable est atteint. En particulier, sur le jeu de données composé de reads de 100 000 paires de bases, la stratégie de segmentation permet de diviser par 171 le temps d’exécution, passant alors de plus de huit jours à légèrement plus d’une heure.
Validation des métriques en mode données réelles
Afin de valider le comportement d’ELECTOR lors de l’évaluation de données réelles, pour comparer les résultats obtenus en mode données simulées aux résultats obtenus en mode données réelles. L’évaluation de chacun de ces jeux de données a ainsi été réalisée deux fois par ELECTOR, après correction des reads avec le module de correction de Canu, en utilisant les paramètres par défaut. En mode données simulées, l’ensemble des fichiers produits lors de la simulation a été fourni en entrée à ELECTOR, et les reads de référence ont alors été retrouvés en analysant les fichiers décrivant les erreurs introduites dans les reads lors de la simulation. En mode données réelles, seul le fichier FASTA décrivant les reads simulés a été fourni en entrée à ELECTOR, et les reads de référence ont alors été retrouvés en alignant les reads simulés sur le génome de référence à l’aide de Minimap, comme si ces reads provenaient d’une réelle expérience de séquençage.
Les résultats de ces expériences montrent que les métriques calculées par ELECTOR en mode données simulées et en mode données réelles sont cohérentes et comparables. En particulier, le rappel, la précision, et le taux d’erreurs sont très similaires entre les deux modes. Cependant, la même tendance que lors de la comparaison à LRCstats est observée, et les deux modes d’évaluation présentent ainsi des différences au niveau des comptes détaillés de chaque type d’erreur, ainsi que de plus importantes différences au niveau des reads reportés comme étant trimmés ou splittés, et de la longueur des régions manquantes dans ces reads.
Ces différences peuvent s’expliquer par les biais induits par l’étape d’alignement additionnelle employée dans le mode données réelles, afin de retrouver les reads de référence. Les principales différences observées entre les deux modes se situent en effet dans les métriques citées ci-dessus, hautement dépendantes des choix réalisés lors de l’alignement. Par ailleurs, les métriques sur les extrémités des reads ayant été clippées lors de cette étape d’alignement, non calculées en mode données réelles, mais calculées en mode données simulées, expliquent également les différences observées entre les métriques des deux modes.
Table des matières
1 Introduction
1.1 Préambule
1.2 Contexte de travail
1.2.1 Le laboratoire LITIS et l’équipe TIBS
1.2.2 Le traitement des données de séquençage
1.3 Contexte de recherche
1.3.1 Projet C3G
1.4 Objectifs
1.5 Organisation du manuscrit
2 Le séquençage de l’ADN
2.1 Introduction
2.2 L’ADN d’un point de vue biochimique
2.3 Technologies de séquençage
2.3.1 Première génération
2.3.2 Deuxième génération
2.3.3 Troisième génération
2.3.4 Remarques et notations
2.3.5 Simulation de reads
2.3.6 Formats des données
2.3.7 Résumé des technologies disponibles
2.4 Point de vue informatique
2.4.1 Notions de combinatoire des mots
2.4.2 Structures de données
2.5 Problématiques
2.5.1 Alignement
2.5.2 Assemblage
2.5.3 Correction
2.6 Synthèse
3 Correction de reads longs
3.1 Introduction
3.2 Correction hybride
3.2.1 Alignement de reads courts sur les reads longs
3.2.2 Alignement de reads longs et d’assemblages de reads courts
3.2.3 Graphe de de Bruijn
3.2.4 Modèles de Markov cachés
3.3 Auto-correction
3.3.1 Alignement multiple
3.3.2 Graphe de de Bruijn
3.4 Synthèse
4 Évaluation des méthodes de correction de reads longs
4.1 Introduction
4.1.1 Contexte
4.1.2 Travaux précédents
4.1.3 Contribution
4.2 Vue d’ensemble
4.3 Premier module
4.3.1 Préparation des triplets
4.3.2 Alignement multiple de triplets
4.3.3 Calcul des métriques d’évaluation à partir de l’alignement multiple
4.4 Second module
4.4.1 Alignement des reads corrigés
4.4.2 Assemblage des reads corrigés
4.5 Résultats
4.5.1 Validation de la stratégie de segmentation
4.5.2 Impact des paramètres
4.5.3 Comparaison avec LRCstats
4.5.4 Évaluation de données réelles
4.5.5 Alignement et assemblage
4.6 Synthèse
5 Correction hybride de reads longs fortement bruités
5.1 Introduction
5.1.1 Contexte
5.1.2 Travaux précédents
5.1.3 Contribution
5.2 Graphe de de Bruijn d’ordre variable
5.2.1 Travaux précédents
5.2.2 PgSA
5.2.3 Représentation
5.3 Chaîne de traitement
5.3.1 Vue d’ensemble
5.3.2 Correction des reads courts
5.3.3 Construction du graphe
5.3.4 Mise en évidence des graines
5.3.5 Extension et liaison des graines
5.3.6 Extension des extrémités
5.3.7 Sortie
5.4 Résultats
5.4.1 Impact des paramètres
5.4.2 Comparaison à l’état de l’art sur données simulées
5.4.3 Comparaison à l’état de l’art sur données réelles
5.4.4 Origine des bases dans les reads longs corrigés
5.5 Synthèse
6 Auto-correction de données ultra-long reads
6.1 Introduction
6.1.1 Contexte
6.1.2 Travaux précédents
6.1.3 Contribution
6.2 Chaîne de traitement
6.2.1 Vue d’ensemble
6.2.2 Définitions
6.2.3 Calcul des chevauchements
6.2.4 Calcul des piles de chevauchements et des fenêtres
6.2.5 Calcul du consensus d’une fenêtre
6.2.6 Réalignement du consensus d’une fenêtre sur le read
6.2.7 Sortie
6.3 Résultats
6.3.1 Validation de la stratégie de segmentation
6.3.2 Outils et jeux de données évalués
6.3.3 Impact de l’étape de raffinement de la correction
6.3.4 Comparaison à l’état de l’art sur données simulées
6.3.5 Comparaison à l’état de l’art sur données réelles
6.3.6 Correction d’assemblages
6.4 Synthèse
7 Benchmark des méthodes de correction de reads longs
7.1 Introduction
7.2 Jeux de données du Chapitre 5
7.2.1 Données simulées
7.2.2 Données réelles
7.3 Jeux de données du Chapitre 6
7.3.1 Données simulées
7.3.2 Données réelles
8 Conclusion et perspectives
8.1 Conclusion
8.1.1 Contributions
8.2 Perspectives
8.2.1 ELECTOR
8.2.2 HG-CoLoR
8.2.3 CONSENT
8.2.4 Perspectives générales
Liste des publications et communications
Bibliographie
