Algorithmes biomoléculaires scalables – Scalmazene

Les protocoles actuels pour résoudre des problèmes à base d'ADN sont limités par un fort taux d'erreur (~1/10.000) et une difficulté à produire un grand nombre de brins d'ADN suffisamment différents pour que la réaction soit sélective. De ce fait, les tailles d'instances résolvables par ces méthodes sont très limitées (typiquement < 10). Nous proposons un protocole expérimental qui brisera cette barrière en résolvant des instances de taille de plusieurs ordres de grandeur supérieure. Nous nous concentrerons sur un problème de graphe: la recherche d'un plus court chemin dans un labyrinthe. Ce protocole, que nous allons réaliser expérimentalement, n'utilise qu'un nombre constant de brins d'ADN, indépendant donc de la taille de l'instance. De plus, il combine aléatoire et déterminisme de sorte que toute erreur est réversible jusqu'à ce qu'une solution correcte soit trouvée. Ceci permet d'augmenter significativement le taux de succès contre un ralentissement très modeste de la réaction.