Relaxations du problème de sériation et applications à l'assemblage de génome de novo

In a sequencing experiment, we can only “read” small fragments (reads) of DNA due to physical limitations, whose location on the genome is unknown. De novo assembly aims to put them together to retrieve the full DNA sequence, like a jigsaw puzzle. The OLC approach computes pairwise Overlaps between reads to find their Layout, and then derive a Consensus sequence. The layout can be cast as an instance of the Seriation combinatorial problem, seeking to reorder a set of elements based on their pairwise similarity, such that similar elements are nearby. In a noiseless setting, a spectral method can solve Seriation efficiently. Still, it often fails on noisy, real DNA data. Notably, assembly is challenged by repeated genomic regions (repeats) causing distant fragments to be similar. Most assembly engines follow hierarchical, greedy schemes, including modules dedicated to detect and disambiguate repeats while constructing the output sequence. We explore a simpler approach using Seriation to lay out all reads at once. Our first contribution is to show that the spectral method can be seamlessly integrated in an OLC framework, yielding competitive results compared to standard methods on real data. However, due to repeats, the method can only find fragmented assemblies (with a few large assembled fragments), i.e., it does not succeed to lay- out all the reads together at once. In our second contribution, we extend the spectral method using a multidimensional spectral embedding. It provides a unifying framework for seriation and circular seriation, a variant searching for a cyclic ordering of the data. This method significantly improves the robustness of the original algorithm on noisy data, and yields single contig assembly of bacterial genomes. As a third contribution, we introduce the Robust Seriation framework, formalizing the task of seriation on corrupted data. We outline the relation between (robust) seriation and other combinatorial problems, particularly for stylized matrices modeling DNA sequencing data. We pro- pose dedicated algorithms that experimentally improve robustness on synthetic and real data, although they turn out to be more sensitive than the method constituting our second contribution. In a fourth contribution, we introduce the problem of Seriation with Duplications, which is motivated by the application of assembling cancer genome from spatial conformation (Hi-C) data. We propose an alternated minimization algorithm that can utilize methods designed to solve Robust Seriation, and evaluate it on toy data.
Les technologies de séquençage d’ADN ne permettent de lire que de courts fragments, dont on ignore la position sur le génome. L’assemblage de novo vise à reconstituer une séquence d’ADN entière en mettant ces fragments bout-à-bout, tel un puzzle. Dans l’approche OLC (overlap-layout-consensus), on calcule le chevauchement entre fragments afin de les disposer en ordre (réarrangement), puis extraire une séquence consensus. Le réarrangement peut s’écrire comme un problème combinatoire de sériation, où l’on réordonne des éléments comparables entre eux, de sorte que deux éléments adjacents sont similaires. Ce problème est résolu efficacement par un algorithme spectral en l’absence de bruit, mais il en va autrement des données génomiques réelles. En particulier, des régions du génome sont similaires bien qu’éloignées (séquences répétées), rendant l’assemblage problématique. Les méthodes d’assemblage emploient des algorithmes hiérarchiques et gloutons pour désambiguïser les séquences répétées. Nous proposons ici une approche épurée où l’on réarrange tous les fragments « d’un coup »via la résolution de sériation. Notre première contribution montre que l’emploi de la méthode spectrale pour le réarrangement s’intègre par- faitement dans le schéma OLC, produisant des résultats de qualité semblable aux méthodes standard. Ce- pendant, du fait des séquences répétées, cette méthode produit des assemblages fragmentés (typiquement en quelques sous-séquences au lieu d’une). La deuxième contribution est un prolongement de la méthode spectrale lié à la réduction de dimension sous conservation de distances, englobant les problèmes de sériation et de sériation circulaire (une variante où les éléments peuvent être ordonnés selon un cycle) dans un cadre unifié. Ce prolongement rend l’algorithme robuste au bruit et résout le problème de fragmentation de l’assemblage précédent. Notre troisième contribution formalise la sériation robuste, où l’on souhaite réordonner des données bruitées. Nous décrivons des liens avec d’autres problèmes combinatoires, en particulier pour des matrices modélisant les données réelles d’ADN. Nous proposons des al- gorithmes adaptés, améliorant expérimentalement la robustesse sur données synthétiques et réelles, bien que moins clairement que la deuxième contribution. La quatrième contribution présente le problème de sériation avec duplication, motivé par l’assemblage de génomes cancéreux via des données de conformation spa- tiale, que nous tentons de résoudre avec un algorithme de projections alternées fondé en partie sur les méthodes de sériation robuste, sur données synthétiques.