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.

Les virus font partie des entités les plus abondantes sur Terre, mais la diversité des virus est très peu connue puisque biaisée en faveur d’hôtes animaux d’intérêts sociétal, agronomique et économique. L’apport des nouvelles techniques de séquençage permet actuellement d’obtenir des informations qui étaient tout simplement inaccessibles. Le but de mon travail de thèse a été l’étude de la diversité virale présente au sein d’un grand nombre d’animaux non-modèles. Pour répondre à cette problématique il m’a fallu mettre en place une méthodologie analytique innovante de découverte de nouveaux virus par une approche de méta-transcriptomique. Ce travail i) montre que la méthodologie bioinformatique mise en place est pertinente, ii) permet de découvrir de nouveaux virus ayant des caractéristiques génomiques particulières relevant de nouveaux genres ou familles de virus, iii) révèle de nouveaux hôtes pour des virus appartenant à des familles virales très étudiées et iv) montre que la gamme d’hôte de virus connus peut être plus étendue qu’attendu grâce à un focus sur la diversité des virus d’hyménoptères. D’une manière plus globale, mon travail permet de combler quelques lacunes existantes dans les connaissances liées à l’étude de la diversité virale et met en évidence l’importance de l’étude des animaux non-modèles. / Viruses are among the most abundant entities on Earth, but the viral diversity remains mostly unknown as currently biased in favour of animals of social, agronomic and economic interest. Next Generation Sequencing technologies provide access to so far inaccessible information. The aim of my PhD thesis was the study of the viral diversity within a large range of non-model animals. To address this question I set up an innovative analytical framework to discover new viruses based on a meta-transcriptomic approach. This work i) shows that this bioinformatics method is efficient and powerful, ii) allows the discovery of new viruses with particular genomic organisations suggesting they belong to new virus genera of families, iii) uncovered new viruses from new hosts in well-known viral families and iv) shows wider viral host range than previously expected based on a particular focus on hymenopteran viral diversity. Overall, my work allows to fill some gaps in the knowledge of viral diversity and shows the importance of studying non-model animal species in virology.