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

Résumé 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.