L'assemblage de séquences génomiques commence par le calcul de superchaines qui forment les /contigs/ à partir des lectures sorties des appareil de séquençage. Ce calcul procède par fusion de lectures selon leur chevauchement.
Une superchaîne d'un ensemble de mots est une chaîne de caractères qui contient tous les mots en entrée comme sous-chaîne.  On construit des superchaînes par fusion de mots en utilisant leurs chevauchements. Par exemple, pour l'ensemble { abba, baabb, aba }, on fusionne baabb et abba en baabba, puis on fusionne ce dernier avec aba, pour obtenir baabbaba, qui est une superchaîne de l'ensemble de départ.  On abordera la question du calcul de la plus courte superchaîne d'un ensemble de mots, une de ses variantes et les graphes qui permettent de la modéliser. J'introduirai les questions de superchaines ainsi qu'un nouveau graphe pour représenter les chevauchements utiles pour construire les superchaines. Je montrerai comment construire ce graphe en limitant l'espace et le temps nécessaires. J'aborderai les questions d'approximation des superchaînes par des algorithmes gloutons. Je terminerai en expliquant comment les applications de nouveaux graphes peuvent être plus performants que les outils d'assemblage les meilleurs du domaine (SPAdes ou IDBA) qui réalisent un assemblage grâce à de multiples graphes de De Bruijn.

Travaux réalisés principalement avec Bastien Cazaux.

Références bibliographiques:

- The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings. Discrete Applied Mathematics 212: 48-60 (2016)
- A linear time algorithm for Shortest Cyclic Cover of Strings. J. Discrete Algorithms 37: 56-67 (2016)
- Superstring Graph: A New Approach for Genome Assembly. AAIM 2016: 39-52
- Superstrings with multiplicities.  Combinatorial Pattern Matching, CPM 2018, LIPIcs 105, 21:1-21:16
- Practical lower and upper bounds for the Shortest Linear Superstring. Symposium on Experimental Algorithms, SEA 2018, LIPIcs 103, 18:1-18:14