Bakterien helfen beim Problem des Handlungsreisenden

Mit einer Art "Brute-Force"-Strategie und Coli-Bakterien haben Forscher gezeigt, wie sich das Problem des Handlungsreisenden attackieren lässt.

In Pocket speichern vorlesen Druckansicht 72 Kommentare lesen
Lesezeit: 1 Min.
Von
  • Christian Kirsch

Wie bereist man eine Menge von Orten so, dass jeder nur genau einmal besucht wird und die Reise möglichst kurz ist? Dieses "Problem des Handlungsreisenden" beschäftigte schon 1736 den Mathematiker Leonhard Euler: Er wollte jede der sieben Brücken Königsbergs über den Fluss Pregel nur ein einziges Mal überqueren und zum Ausgangspunkt zurückkehren. Mit seinen Überlegungen initiierte er die Graphentheorie.

Eine Gruppe von Forschern hat nun die unter anderem im menschlichen Darm lebenden E.-Coli-Bakterien so "programmiert" (PDF-Datei), dass sie einen "Hamilton-Zyklus" in einem Graphen mit nur drei Knoten fanden. Diese Knoten repräsentierten sie durch miteinander verbundene Hälften zweier Gene, die rote beziehungsweise grüne fluoreszierende Proteine erzeugen. Bakterien, die den gesuchten Pfad gefunden hatten, enthielten beide Gene und fluoreszierten deshalb gelb.

Der Hamilton-Zyklus ist ein Kreis, der alle Knoten eines gegebenen Graphen genau einmal enthält. Die Aufgabe, ihn zu ermitteln, gehört zur Klasse der NP-vollständigen Probleme. Ein deterministischer Algorithmus erfordert einen mit der Menge der Knoten exponentiell wachsenden Aufwand. Statt so eines deterministischen Verfahrens setzt die Bakterienmethode auf das Ausprobieren einer großen Zahl von Lösungswegen. (ck)