Cette thèse s'inscrit dans le cadre du traitement des données issues de séquençage haut débit, et en particulier des données produites en metabarcoding ADN. Le metabarcoding ADN consiste à identifier des taxons ou des groupes taxinomiques à partir de l'ADN présent dans des échantillons environnementaux (eau, sol, fèces...). Après extraction de l'ADN, de courtes séquences utilisées comme marqueurs taxinomiques sont amplifiées par PCR puis séquencées en utilisant les nouvelles techniques de séquençage haut débit. De très importants volumes de données sont ainsi générés, le plus souvent, de plusieurs milliers à plusieurs centaines de milliers de séquences par échantillon. L'objectif principal de cette thèse était le développement de méthodes d'analyse de ces séquences. Les méthodes de classification permettent de traiter de nombreuses problématiques en metabarcoding ADN. La classification supervisée est utilisée pour assigner les séquences à des taxons en les comparant aux séquences de bases de données de référence. Les méthodes de classification non supervisée permettent de créer des groupes taxinomiques (MOTU) à partir des séquences, afin de faire des estimations de biodiversité. Ces méthodes sont aussi employées pour identifier les séquences erronées produites par la PCR et le séquençage notamment, où les séquences erronées dérivent souvent des vraies séquences et leur sont très similaires. Les méthodes de classification demandent une méthode de comparaison des séquences qui soit idéalement à la fois très rapide et exacte. Une telle méthode a été développée, en utilisant un algorithme d'alignement global de type Needleman-Wunsch calculant la longueur de la plus longue sous-séquence commune entre les séquences à aligner, associé à un filtre sans perte permettant d'éviter l'alignement de certaines paires de séquences n'ayant aucune chance de présenter une similarité supérieure à un seuil choisi. L'utilisation d'instructions Single Instruction, Multiple Data, de même que le multithreading optionnel des calculs, permettent d'associer rapidité et exactitude. Cette méthode de comparaison est implantée dans SUMATRA, un programme calculant toutes les similarités deux à deux d'un jeu de données ou entre deux jeux de données, avec possibilité de fixer un seuil de similarité en dessous duquel les similarités ne sont pas rapportées. Elle est aussi utilisée dans SUMACLUST. SUMACLUST est un programme regroupant les séquences en utilisant un algorithme de clustering en étoile, où chaque groupe possède une séquence représentative. Il peut être utilisé pour créer des MOTU, ou pour détecter les séquences erronées dérivant de vraies séquences. Plus spécialisé, le programme SUMACLEAN a été développé pour détecter les séquences contenant des erreurs ponctuelles de PCR. Pour cela, des graphes orientés acycliques sont générés, dont la topologie correspond parfaitement aux cascades d'erreurs générées par les erreurs ponctuelles de PCR. Par ailleurs, une réflexion a été menée pour le développement d'une nouvelle approche de classification supervisée pour l'assignation taxinomique des séquences. Aujourd'hui, la plupart des approches d'assignation utilisent des méthodes mal adaptées au polymorphisme important des marqueurs, et ne considèrent pas suffisamment l'incomplétude et les erreurs inhérentes aux bases de données de référence. Une nouvelle approche a été testée, basée sur l'idée d'un départ depuis la racine de l'arbre taxinomique, suivi d'une descente jusqu'à un arrêt possible lorsque descendre à un niveau taxinomique plus précis semble irraisonnable. Cela permettrait en théorie de mieux gérer les problèmes inhérents aux bases de données de référence, mais pose le problème de la représentation des séquences aux différents niveaux de l'arbre, et du modèle de choix du chemin à prendre, pour lesquels aucune solution complètement satisfaisante n'a été trouvée à ce jour. / This thesis positions itself in the context of the processing of high-throughput sequencing data, and specifically DNA metabarcoding data. DNA metabarcoding consists of the identification of taxa or taxonomic groups from DNA extracted from environmental samples (water, soil, animal feces). After extraction of the DNA, short sequences used as taxonomic markers are amplified by PCR, then sequenced using high-throughput sequencing technologies. Important volumes of data are produced that way, usually from several thousands to several hundreds of thousands sequences per sample. This thesis aimed for the development of methods for the analysis of these sequences. Classification methods allow the treatment of numerous problems in DNA metabarcoding. Supervised classification is used for the taxonomic assignment of sequences to taxa, by comparing them to the sequences of a reference database. Unsupervised classification methods are used to create taxonomic groups (MOTUs) from the sequences, in order to estimate biodiversity. They are also used to identify the erroneous sequences generated during the PCR and sequencing steps in particular, where erroneous sequences often derive from true sequences and remain very close to them. Classification approaches used in the context of DNA metabarcoding necessitate a sequence comparison method that should be both fast and exact. Such a method was developed, using a Needleman-Wunsch type global alignment algorithm computing the length of the longest common subsequence between the two sequences being aligned, associated with a lossless filter allowing to avoid the alignment of some pairs of sequences that have no chance to present a similarity superior to a chosen threshold. The use of Single Instruction, Multiple Data instructions, as well as the availability of multithreading speed up the calculations. This comparison method is implanted in SUMATRA, a program computing all the pairwise similarities of a dataset or between two datasets, with the possibility to set a threshold under which similarities are ignored. It is also used in SUMACLUST, a program grouping sequences using a star clustering algorithm, where each cluster possesses a representative sequence. This algorithm can be used to generate MOTUs, or to identify erroneous sequences deriving from true sequences, by using the fact that true sequences tend to end up as the representative sequences of their cluster. More specialized, the SUMACLEAN program was developed to identify sequences containing ponctual PCR errors. To that end, directed acyclic graphs are created, whose topology matches perfectly the successions of errors generated by ponctual errors during PCR. A new approach for the taxonomic assignment of sequences with a supervised classification method was also studied. Nowadays, most taxononomic assignment approaches use methods that are badly suited for the important polymorphism of markers, and don't take in account enough the incompleteness and errors inherent to reference databases. A new approach was tested, based on the idea of a start from the root of the taxonomic tree, and a descent in it with a possible stop before reaching a leaf, if descending to a more precise taxonomic level seems unreasonable. This approach would theoretically allow for a better handling of the problems inherent to reference databases, but poses a few issues, such as the representation of sequences at intermediate tree levels, and the model used to make choices regarding the path to take in the tree, for which no satisfying solutions have been found yet.
| Identifer | oai:union.ndltd.org:theses.fr/2015GREAV060 |
| Date | 31 March 2015 |
| Creators | Mercier, Celine |
| Contributors | Grenoble Alpes, Coissac, Éric |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0024 seconds