Algorithmique des pavages auto-assemblants

Benoît Masson

Les différentes propriétés chimiques de l'ADN, bien maîtrisées expérimentalement, en font un outil particulièrement intéressant d'un point de vue informatique. En effet, on pourrait théoriquement utiliser de l'ADN comme élément de base d'ordinateurs d'un genre nouveau, permettant de faire des calculs massifs en parallèle et à moindre coût : c'est ce qu'on appelle le « DNA computing ».
Nous nous intéresserons au cas des pavages, où les tuiles de base sont des carrés constitués de brins d'ADN, et dont les côtés sont « collants ». Plongées dans une solution, ces tuiles vont se lier les unes aux autres d'elles-mêmes, sans contrôle extérieur, pour finalement assembler une forme microscopique prédéfinie. Les questions que l'on peut alors se poser sont les suivantes : comment minimiser le nombre de colles (donc de tuiles) permettant d'obtenir la forme désirée, le plus rapidement possible, en minimisant l'impact des erreurs ?
Nous étudierons un problème classique, l'assemblage d'un carré de taille n x n. Nous commencerons par examiner le modèle initial dû à Erik Winfree (aTAM), puis nous introduirons différentes extensions naturelles permettant d'améliorer ces résultats.