Franck Mée,25 Juillet 2009 16h50

Quoi de plus éloigné que la gravure de galettes de silicium et l'élevage de bactéries ? Pourtant, il y a des points communs : le Journal of biological engineering publie les travaux d'une équipe qui a fait résoudre un problème classique de l'informatique par une colonie de Escherichia coli.

La recherche d'un chemin hamiltonien dans un graphe... Voilà qui rappellera des souvenirs à tous les anciens étudiants en informatique. Pour les autres, un chemin hamiltonien est un moyen de passer par tous les sommets une et une seule fois -- une modélisation abstraite d'un problème bien connu des facteurs : livrer le courrier à toutes les adresses mais si possible sans repasser dans la même rue.

Ce problème pose un soucis pour l'informatique : sur un graphe restreint, tout va vite, mais chaque augmentation même modeste de la complexité du graphe entraîne une explosion du temps de calcul nécessaire.

L'ordinateur biologique

Une équipe associant biologistes, mathématiciens et informaticiens d'universités du Missouri et de Caroline du Nord ont démontré la possibilité de confier le problème non à du silicium, mais à Escherichia coli, bactérie bien connue de nos intestins et très utilisée en recherche biologique.

En effet, ils ont pu utiliser ces bactéries pour leur faire «calculer» un chemin hamiltonien dans un graphe de... trois sommets.

Ils ont pour cela «encodé» le graphe dans le génome d'une bactérie, chaque sommet correspondant à la synthèse d'une substance fluorescente rouge ou verte. Initialement, l'encodage est sans ordre particulier, et les E. coli étaient soit «éteintes», soit rouges.

Cependant, au fil des reproductions, les E. coli recombinent leur génome : des morceaux de gènes sont échangés, leur ordre modifié. Et après quelques générations de cette évolution, sont apparues des bactéries dans lesquelles le génome était bien ordonné pour synthétiser la fluorescence verte et la rouge : ces bactéries s'éclairaient donc en jaune. Il suffisait dès lors de «lire» le génome de ces bactéries pour obtenir la solution du problème.

Bien entendu, la performance est pour l'heure modeste. Mais cela démontre qu'il est possible de faire calculer des solutions par des bactéries, devenues en quelque sorte des processeurs d'un ordinateur génétique. Or, pour ce type de problème, cette voie de recherche paraît prometteuse : à chaque génération (toutes les 20 minutes environ dans le cas de E. coli), le nombre de bactéries double, et donc la puissance de calcul -- ou plus exactement la possibilité qu'une d'entre elles représente la solution.

Question de complexité

Pour un ordinateur classique, la seule solution est d'explorer les chemins existants. Il faut donc parcourir un très grand nombre d'arcs pour s'apercevoir que le chemin suivi n'est pas une solution (on retombe sur un sommet déjà parcouru, ou l'on arrive à un cul-de-sac sans avoir fait le tour du graphe). Le temps de calcul évolue en fonction de... la factorielle du nombre de sommets.

Dans le cas de l'ordinateur biologique, en revanche, l'ordinateur croît en même temps que le problème, doublant sa performance toutes les 20 minutes. Le temps de calcul évolue alors de façon logarithmique avec l'augmentation du nombre de sommets ; même si E. coli calcule moins vite qu'un processeur moderne, elle va rapidement le rattraper du fait de sa multiplication.

Ce n'est bien entendu pas tout de suite que les bactéries vont remplacer les ordinateurs, et elles ne seront jamais aussi efficaces que les semi-conducteurs pour les tâches courantes. Mais voilà qui ouvre une voie intéressante vers une approche différente de certains calculs...