Un ordinateur bactérien pour la théorie des graphes

Un problème algorithmique bien connu en informatique est la recherche d'un chemin hamiltonien, c'est-à-dire un trajet passant une seule fois par tous les sommets d'un graphe. Pour les ordinateurs classiques, la complexité explose avec la taille du graphe, nécessitant un temps de calcul proportionnel à la factorielle du nombre de sommets.

Une équipe pluridisciplinaire (biologistes, mathématiciens et informaticiens) a démontré une approche radicalement différente : faire résoudre le problème par une colonie de bactéries E. coli. Ils ont encodé le graphe dans le génome bactérien, où chaque sommet correspond à la synthèse d'une protéine fluorescente. Au fil des reproductions et recombinaisons génétiques, des bactéries ont progressivement acquis un génome ordonné produisant la solution (détectable par la fluorescence jaune).

Bien que la performance actuelle soit modeste (test sur trois sommets), cette approche offre un avantage théorique remarquable : la population bactérienne double tous les 20 minutes environ, multipliant exponentiellement la puissance de calcul. Le temps de calcul évolue alors logarithmiquement avec la complexité, bien plus favorable qu'un ordinateur classique. Cela ouvre une voie prometteuse pour certains problèmes combinatoires, même si les bactéries ne remplaceront jamais les semi-conducteurs pour les tâches usuelles.