Après une interruption due aux conditions sanitaires, les Leçons de Mathématiques et d'Informatique d'Aujourd'hui reprendront en présentiel. Ainsi, une leçon sera donné par Eric Rivals (LIRMM) :

le jeudi 14 avril, 16h-18h (avec une pause à 17h), 

l'amphi B du bâtiment A29. 

Superchaînes: des chevauchements entre mots aux  graphes d'assemblage.

Eric Rivals - LIRMM, CNRS, Univ. Montpellier
https://www.lirmm.fr/~rivals/

Les progrès fantastiques des technologies de séquençage de l'ADN ont accru le volume de séquençage de façon sensationnelle (le stockage des données de séquençage est aujourd'hui un défi technique et organisationnel), mais les séquenceurs modernes buttent toujours sur la difficulté à lire de longues séquences d'ADN.  Ainsi, au lieu de produire la séquence complète -- d'un seul tenant -- de la molécule d'intérêt (par ex. un chromosome entier), le séquençage ne délivrent que les séquences des fragments de l'ADN -- de quelques dizaines à quelques milliers de nucléotides de long -- mais en quantité astronomique. Pour reconstruire la séquence complète du chromosome voulu, on va fusionner les séquences des fragments selon leurs chevauchements. En termes mathématiques, on calcule une /superchaîne/ des fragments en entrée. Le problème de la plus courte superchaîne d'un ensemble de mots est apparu dans ce contexte à la fin des années 70. Cependant, cette question a été étudiée et utilisée dans bien d'autres applications (l'ordonnancement de tâches ou la compression de texte, par exemple), ainsi que pour son lien avec le problème du voyageur de commercie (/Travelling Salesman Problem/ en anglais).

Dans ce cours, je présenterai la question du calcul d'une plus courte superchaîne, et ses variantes, et aborderai les difficultés qu'elles posent, leur complexité, la recherche de solutions approchées et les liens avec les graphes de représentations des chevauchements. En particulier, je m'appesantirai sur le calcul de plus courte couverture cyclique, une variante centrale dans de nombreux algorithmes d'approximation de la plus courte superchaîne. D'autre part, j'aborderai les algorithmes de construction des graphes utilisés pour le calcul de superchaînes, afin d'exhiber le lien avec des structures d'indexation de texte. Enfin, je conclurai en citant des extensions des questions de superchaînes qui s'attaquent à des spécificités pratiques, et quelques questions ouvertes.