Nouvelles approches pour l'exploitation des données de sequençage haut débit

In this thesis we discuss computational methods to deal with DNA sequences provided byhigh throughput sequencers. We will mostly focus on the reconstruction of genomes fromDNA fragments (genome assembly) and closely related problems. These tasks combinehuge amounts of data with combinatorial problems. Various graph structures are usedto handle this problem, presenting trade-off between scalability and assembly quality.This thesis introduces several contributions in order to cope with these tasks. First,novel representations of assembly graphs are proposed to allow a better scaling. We alsopresent novel uses of those graphs apart from assembly and we propose tools to use suchgraphs as references when a fully assembled genome is not available. Finally we show howto use those methods to produce less fragmented assembly while remaining tractable.Cette thèse a pour sujet les méthodes informatiques traitant les séquences ADN provenantdes séquenceurs haut débit. Nous nous concentrons essentiellement sur la reconstructionde génomes à partir de fragments ADN (assemblage génomique) et sur des problèmesconnexes. Ces tâches combinent de très grandes quantités de données et des problèmescombinatoires. Différentes structures de graphe sont utilisées pour répondre à ces prob-lèmes, présentant des compromis entre passage à l’échelle et qualité d’assemblage.Ce document introduit plusieurs contributions pour répondre à ces problèmes. Denouvelles représentations de graphes d’assemblage sont proposées pour autoriser un meilleurpassage à l’échelle. Nous présentons également de nouveaux usages de ces graphes, dif-férent de l’assemblage, ainsi que des outils pour utiliser ceux-ci comme références dans lescas où un génome de référence n’est pas disponible. Pour finir nous montrons commentutiliser ces méthodes pour produire un meilleur assemblage en utilisant des ressourcesraisonnables