Yann Ponty (LIX, Ecole Polytechnique)

La structure secondaire est une représentation discrète de la (ou les) conformation(s) adoptée(s) par une {w i ,w j } ∈ {{A,U},{C,G},{G,U}}. De plus, deux paires ( i , j ) et ( i ‘, j ‘), i ‘≤ j , doivent satisfaire une relation d’imbrication ( i < i ‘< j < j ‘) ou de précédence ( i < j < i ‘< j ‘). Les objets combinatoires associés sont en bijection avec de nombreuses classes combinatoires, tels les mots de Motzkin sans pics, ou encore des arbres planaires où les noeuds internes comptent double pour la taille.

Dans une première partie, nous survolerons certaines applications de la combinatoire analytique afin d’extraire des propriétés asymptotiques de ce biopolymère fascinant, ainsi que divers algorithmes de programmation dynamique utilisés pour en analyser le repliement. Au coeur de ces applications apparemment distinctes, on retrouve les même schémas de décomposition de l’espace de recherche, permettant d’entrevoir une unification, pour toute une classe de problèmes combinatoires, de l’analyse et de la conception d’algorithmes efficaces pour une instance donnée. Nous illustrerons ce programme de recherche sur le problème de l’alignement d’arbre, pour lequel nous avons récemment obtenu la première décomposition non-ambiguëe avec Courtiel et Chauve.

Nous considérerons ensuite le problème du design d’ARN, c’est à dire la conception d’une séquence d’ARN adoptant une structure secondaire prédéterminée comme structure d’énergie minimale. Nous décrirons quelques classes de structures secondaires pour lesquelles le problème peut être résolu en temps linéaire. La mise en évidence d’obstructions, ie de motifs locaux rendant impossible le design, soulève des questions de combinatoire analytique/symbolique en lien avec un modèle populaire d’évolution théorique.

Enfin, si le temps le permet, nous présenterons quelques résultats préliminaires sur le multidesign, une version du design où le critère d’optimalité est relâché, et où la séquence produite doit être compatible, au sens des paires de bases, avec un ensemble de structures secondaires ciblées. On considère alors le graphe G sur [1, n ] dont les arêtes sont les paires de bases comprises dans les structures ciblées. De façon surprenante, le nombre de séquences solutions du multidesign est égal, à un facteur 2 près, au nombre d’ensembles stables. Cela implique la #P-complétude du problème de comptage associé, et motive la conception d’un algorithme FPT en O(2 W n ), où W est la largeur arborescente de G et n la longueur de l’ARN, pour la génération aléatoire de séquences solutions.