Note ABES Algorithmes bio-informatiques pour l’analyse de données de séquençage à haut débit New algorithmic and bioinformatic approaches for the analysis of data from high throughput sequencing Méta-génomique Méta-transcriptomique 005.74 Bioinformatique Algorithmes d'approximation Génomique Séquençage des acides nucléiques Transcriptome Les algorithmes d'alignement sont au coeur de l'analyse de séquences en bio-informatique. Dans cette thèse, nous nous focalisons sur le problème de l'alignement de lectures, des millions de courtes séquences produites par les séquenceurs de nouvelle génération (NGS) en particulier pour l'analyse de données de métatranscriptome et de métagénome en biodiversité. Pour cela, il y a deux types de difficulté. Le premier est que toutes les technologies NGS entrainent des erreurs de séquençage, telles que substitutions, insertions et suppressions de nucléotides. Le second est que les échantillons métagénomique peuvent contenir des centaines d'organismes inconnus et que leur analyse demande de procéder à des alignements avec des d'espèces possiblement distantes. Pour résoudre ces problèmes, nous avons développé un nouvel algorithme d'alignement reposant sur des graines avec erreurs. Cela amène un gain en sensibilité par rapport aux logiciels existants optimisés pour le problème du reséquençage, avec des similarités élevées et qui se fondent sur des graines exactes. Nous proposons également une nouvelle méthode d'indexation basée sur le Burst trie qui permet d'optimiser la recherche avec les graines avec erreurs. Nous montrons l'efficacité de nos méthodes dans deux nouveaux outils, SortMeRNA pour l'identification d'ARN ribosomiques dans des données de métatranscriptome, et SortMeDNA pour l'alignement de lectures en génomique et métagénomique. Sequence alignment algorithms are at the heart of bioinformatic sequence analysis. In this thesis we focus on the alignment of millions of short sequences produced by Next-Generation Sequencing (NGS) technologies in particular for the analysis of metagenomic and metatranscriptomic data, that is the DNA and RNA directly extracted for an environment. Two major challenges were confronted in our developed algorithms. First, all NGS technologies today are susceptible to sequencing errors in the form of nucleotide substitutions, insertions and deletions. Second, metagenomic samples can contain hundreds of unknown organisms and the standard approach to identifying them is to align against known closely related species. To overcome these challenges we designed a new approximate matching technique based on the universal Levenshtein automaton which quickly locates short regions of similarity (seeds) between two sequences allowing 1 error of any type. Using seeds to detect possible high scoring alignments is a widely used heuristic for rapid sequence alignment, although most existing software are optimized for performing high similarity searches and apply exact seeds. Furthermore, we describe a new indexing data structure based on the Burst trie which optimizes the search for approximate seeds. We demonstrate the efficacy of our method in two implemented software, SortMeRNA and SortMeDNA. The former can quickly filter ribosomal RNA fragments from metatranscriptomic data and the latter performs full alignment for genomic and metagenomic data. Electronic Thesis or Dissertation Text en PDF 2815800 application/pdf https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2013/50376-2013-Kopylova.pdf https://theses.fr/2013LIL10181/abes Kopylova Evguenia Kopylova 1987-01-18 CA 180723642 https://theses.fr/2013LIL10181 2013LIL10181 https://doi.org/10.70675/d813521ez8cd6z44f2zbfc0z496abd81179d 2013-12-11 Informatique Lille 1 026404184 Doctorat Docteur es non oui Touzet Hélène MADS_DIRECTEUR_DE_THESE_1 10394074X Noé Laurent MADS_DIRECTEUR_DE_THESE_2 093601948 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Laboratoire d'informatique fondamentale de Lille (2002-2014) MADS_PARTENAIRE_DE_RECHERCHE_1 077703553 ddc:000 Touzet Hélène Noé Laurent École doctorale Sciences pour l'Ingénieur (Lille) Laboratoire d'informatique fondamentale de Lille (LIFL) PDF 2815800