RECANATI Antoine

Lors d'une expérience de séquençage, nous ne pouvons "lire" que de petits fragments (reads) d'ADN, en raison de limitations physiques, dont la localisation sur le génome est inconnue. L'assemblage de novo vise à les assembler pour retrouver la séquence complète de l'ADN, comme un puzzle. L'approche OLC calcule les chevauchements par paires entre les lectures afin de trouver leur disposition, puis de dériver une séquence consensuelle. La disposition peut être considérée comme une instance du problème combinatoire de la sériation, qui cherche à réorganiser un ensemble d'éléments en fonction de leur similarité par paire, de sorte que les éléments similaires soient proches. Dans un environnement sans bruit, une méthode spectrale peut résoudre efficacement la sériation. Cependant, elle échoue souvent sur des données d'ADN réelles et bruyantes. L'assemblage est notamment mis à mal par les régions génomiques répétées (répétitions), qui font que des fragments éloignés sont similaires. La plupart des moteurs d'assemblage suivent des schémas hiérarchiques et avides, incluant des modules dédiés à la détection et à la désambiguïsation des répétitions tout en construisant la séquence de sortie. Nous explorons une approche plus simple utilisant la sériation pour disposer toutes les lectures en une seule fois. Notre première contribution est de montrer que la méthode spectrale peut être intégrée de manière transparente dans un cadre OLC, donnant des résultats compétitifs par rapport aux méthodes standard sur des données réelles. Cependant, en raison des répétitions, la méthode ne peut trouver que des assemblages fragmentés (avec quelques gros fragments assemblés), c'est-à-dire qu'elle ne parvient pas à disposer toutes les lectures ensemble en une seule fois. Dans notre deuxième contribution, nous étendons la méthode spectrale en utilisant un encastrement spectral multidimensionnel. Elle fournit un cadre unifié pour la sériation et la sériation circulaire, une variante recherchant un ordre cyclique des données. Cette méthode améliore significativement la robustesse de l'algorithme original sur des données bruitées, et permet d'assembler des contigs uniques de génomes bactériens. En troisième lieu, nous introduisons le cadre de la sériation robuste, qui formalise la tâche de sériation sur des données corrompues. Nous soulignons la relation entre la sériation (robuste) et d'autres problèmes combinatoires, en particulier pour les matrices stylisées modélisant les données de séquençage de l'ADN. Nous proposons des algorithmes dédiés qui améliorent expérimentalement la robustesse sur des données synthétiques et réelles, bien qu'ils s'avèrent plus sensibles que la méthode constituant notre deuxième contribution. Dans une quatrième contribution, nous introduisons le problème de la sériation avec duplications, qui est motivé par l'application de l'assemblage du génome du cancer à partir de données de conformation spatiale (Hi-C). Nous proposons un algorithme de minimisation alternée qui peut utiliser des méthodes conçues pour résoudre la sériation robuste, et nous l'évaluons sur des données jouets.

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.