New algorithmic and bioinformatic approaches for the analysis of data from high throughput sequencing

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