Florent Becker (LIFO, Univ. Orléans)

‐ 10:45

De tout temps, femmes et hommes ont aspiré à des nano-colifichets en ADN. Depuis les années 1990, dans la suite des travaux séminaux de Reif, Adleman, Winfree, puis Rothemund et tant d’autres, ils et elles sont exaucés: par une conception astucieuse de mots sur l’alphabet {A, C, T, G}, il est possible d’obtenir des séquences d’ADN dont les interactions ressemblent à de petites tuiles flottant sur un plan discret. Ces tuiles portent des couleurs sur leurs quatre côtés — des séquences d’ADN. Telles des coraux sur un récif, leurs concrétions s’agrègent autour d’une graine: chaque fois qu’une tuile passe à proximité d’une position du bord dont le voisinage est propice, elle se fixe au motif. Année après année, la sophistication des motifs obtenus par ce procédé d’auto-assemblage s’est accrue, donnant naissance aux «self-assembly studies», avec la question des liens entre possibilité de calcul et géométrie de l’objet à assembler. Je présenterai l’énoncé de la caractérisation des fractales auto-assemblables (nec plus ultra du domaine), et l’outil central pour la borne inférieur: le théorème de l’espalier. Ce lemme de pompage établit une relation entre largeur arborescente bornée et limitation du calcul plutôt attendue, mais subtile à caractériser précisément. De plus, sa preuve nous emmènera à la découverte d’outils et de raffinements liés à l’asynchronisme inhérent aux systèmes d’auto-assemblage:

  • la largeur arborescente connexe qui permet de contrôler la décomposition d’un graphe y compris quand certaines parties sont nettement plus arborescentes que d’autres, et d’obtenir une décomposition qui ne crée pas de distortion trop importante de ce graphe;

  • les séquences d’assemblage ordinales pour dompter la concurrence entre plusieurs séquence potentiellement infinies de transitions et définir un ordre de priorité entre elles;

  • la généralisation des assemblages à des graphes qui ne soient pas des sous-graphes du plan euclidien discret , de sorte à éviter les collisions, couplée à une mesure de l’effervescence (la propension à créer des trous) pour se ramener au cas de Z^2.