Graphe de Chevauchements pour les Algorithmes d'Assemblage et de Scaffolding : Etat de l'Art des Paradigmes et Propositions d'Implementations

Assembling Deoxyribonucleic Acid (DNA) fragments based on their overlaps remains the main assembly paradigm with long DNA fragments sequencing technologies, independently of the aim to resolve only one or several haplotypes. Since an overlap can be seen as a succession relationship between two oriented fragments, the directed graph structure has emerged as the more appropriate data structure for handling overlaps. However, this graph paradigm did not appear to take benefit of the reverse symmetry of the orientated fragments and their overlaps, which is a result of blind DNA doublestrand sequencing. Thus, the bi-directed graph paradigm was introduced to be the one that reduces the graph size by handling the reverse symmetry, and since becomes the mainly used graph paradigm. Nevertheless, graph paradigms have never been contrasted before, and no implementations were described. Here we make a complete review on the existing overlap graph paradigms. Furthermore, we present different implementations that are theoretically compared in terms of memory, and their impact on the design and on the time of some basic graph algorithms. We also show that by adapting close logic implementations, a graph paradigm can be switched to another