Abstract
Whole genome can not be read by the current sequencing technologies. Instead, the output is short sequences which are portions with errors of the whole genome. One must then proceed to an assembly of these sequences (called read) to find the sequence of the complete genome. A theoretical version of this problem is the problem of the shortest superstring: given a set of words (own set of reads), we try to find the shortest string that contains all others as substring (the genome of origin). Studied since the 60s, this problem is notoriously difficult to solve by both exactly and approximate methods.Genome assembly requires some reads preprocessing, such as the correction of errors introduced by the sequencing. Some correction softwares (or other pre-treatments) use an indexing data structure of the sequences to localize errors. However, after the correction, this data structure is lost and the assembly uses only the corrected reads. In this thesis, we wonder how to use indexing structures to facilitate or to improve the quality of the genome assembly.First, we show that the graphs used in assembly algorithms could quickly rebuild from an indexing structure (de Bruijn graph, contracted de Bruijn graph and overlap graph). In addition, we present a new graph which summarizes the information of conventional assembly graphs and that we call the hierarchical overlap graph.Secondly, we wondered how an indexing data structure could directly help to solve the theoretical problem of the shortest superstring. For this purpose, we study the solutions that the greedy algorithm gives to this problem (their approximation, their combinatorics, ...) and many of these variants (reverse complement case, cyclic superstring case, case cover by a set of superstrings). This has solved several questions about the complexity and the approximation of these problems. In particular, the greedy algorithm solves in linear time the question of the shortest cyclic cover of strings. Although the greedy algorithm is the simplest and one of the most studied of these problems, it remains a mystery. Our study has highlighted a new graph, the superstring graph, which corresponds to a dip from solutions of the greedy algorithm in the index structure that is the suffix tree. In other words, the superstring graph summarizes all the greedy solutions in a linear space.Finally, attention has turned to the algorithms of the best assemblers used in practice (IDBA, Spades), which have improved the assembly of short reads using several assembly graphs. We show firstly that the superstring graph can store more information than these assemblers and with a complexity in much smaller space. Then, it is apparent that the greedy algorithm for a variant of the shorter superstring problem provides sequences which include the contigs found for these algorithms. These results link the assembly in practice and the superstring problems, and give a strong theoretical framework for studying these heuristic algorithms.