Homepage - FAQ der Informatik.Ger - Biologisches Rechnen

FAQ der Informatik.Ger

Biologisches Rechnen

Kann jemand zu diesem Zeitschriftenartikel etwas Näheres sagen?

If you are interested in the theory of computation, you should look at the November 11, 1994, issue of "Science". In there, Leonard Adleman describes how the structure of the DNA molecule gives an elegant solution to the "directed Hamiltonian path problem" - i.e., the travelling salesman problem. This suggests that biological structures offer the solution to an entire class of NP-complete problems, a fact which is of great significance to the theory and practice of computing. As Adleman puts it, "Here the possibility of computing directly with molecules is explored."

Zunächst mal: Das Hamiltonsche Problem ist nicht das oben genannte Problem des Handlungsreisenden, es gehört nur zur selben Aufwandsklasse, nämlich den NP-vollständigen Problemen. Gegeben ist ein Graph mit gerichteten Kanten, gesucht ein Hamiltonscher Kreis, d.h.: Ein Weg, der jeden Knoten genau einmal durchquert.

Zur Erinnerung: Ein NP-vollständiges Problem ist eines, für das ein nichtdeterministischer Algorithmus mit polynominaler Laufzeit existiert, bisher aber kein deterministischer Algorithmus. mit polynominaler Laufzeit. Außerdem gilt, daß wenn man für irgendein NP-vollständiges Problem jemals einen solchen deterministischen polynominalen Algorithmus finden sollte, damit für alle NP-vollständigen Probleme ebenfalls deterministische, polynominale Algorithmen existieren.

Adleman versucht sich erst gar nicht daran, die NP-Vollständigkeit zu knacken, sondern geht von vornherein an die Umsetzung eines einfachen, nichtdeterministischen Algorithmus, der in 5 Schritten abläuft:

Erzeuge zufällig Pfade.
Behalte nur die Pfade, die am gewünschten Anfangsknoten beginnen und am gewünschten Endknoten enden.
Behalte nur die Pfade, die außerdem exakt n Knoten berühren.
Behalte nur die Pfade, die außerdem jeden Knoten des Graphen mindestens einmal berühren.
Falls Pfade übrigbleiben, gib "Ja" aus, sonst "Nein".

Insofern ist der Versuch vom Standpunkt der theoretischen Informatik her uninteressant; interessant wird er dadurch, daß die Umsetzung in eine biochemische Reaktion extrem effizient ist, da die massive Parallelität der Natur und ihre Minidimensionen voll zur Geltung kommen. Adleman schätzt, daß dieser "Bioalgorithmus" etwa 8 Zehnerpotenzen (!) leistungsfähiger arbeiten könnte, als sein Computergegenstück auf einem Hochleistungsrechner [was bei exponentieller Aufwandsklasse aber nicht viel heißt!]. Außerdem ist der Bioalgorithmus "energiesparend", weil er pro Joule Energie etwa 2*10^19 "Rechenoperationen" ausführen kann, ein Hochleistungscomputer aber nur etwa 10^9. Merkt man an, daß das theoretische Maximum nach den Gesetzen der Thermodynamik bei 34*10^19 Operationen liegt, so sieht man, daß 4 Milliarden Jahre Evolution schon einiges an Optimalität erreicht haben...

Auch die Informationsspeicherdichte (gegenüber beispielsweise Magnetbändern) liegt 12 Zehnerpotenzen besser. DAS sind die wirklich interessanten Dinge an Adlemans Versuch: Daß es prinzipiell möglich ist, mit Biochemie künstliche DNA zu kodieren, die "ablauffähige" Programme bildet, diese ausgeführt und ausgewertet werden können und daß das ganze miniaturisiert auf Molekülebene abläuft.

Adlemans Biologenschreibweise kapiere ich nicht ganz (bin ich Molekularbiologe?), aber mit meinen bescheidenen Biokenntnissen verstehe ich seine Algorithmenumsetzung so: Für jeden Knoten des Graphen verwendet er eine zufällige, 20 Nukleinsäurensequenzen lange, individuelle Proteinkette. Für die Kanten des Graphen erzeugt er die passenden Komplementärketten (ein Endstück von Sequenz(i), ein Anfangsstück von Sequenz(j), zusammenpappen, die Aminosäuren komplementieren). Setzt man nun den Replikationsmechanismus in Gang, so können die so erzeugten Schablonen passende 20-Element-"Legosteine" aus dem Reagenzglas fischen und untereinander verbinden: Milliarden zufälliger Pfade entstehen. (Adleman schätzt die Anzahl "Legosteine" in seinem Versuch auf 30 Billionen Exemplare je Knoten...)

Der "Rest" entspricht biochemischen Aussortierschemata, die mit entsprechenden Abläufen erreicht wurden: Extraktion durch binden an bestimmte Suchproteine. Durch sogenannten "Polymerase - Kettenreaktionen" kann nicht nur die sukzessive Aussortierung der unerwünschten und Verstärkung der gewünschten "Pfade" gesteuert werden, sondern im letzten Schritt kann die gefundene Proteinkette auch zerlegt und damit analysiert werden.

Von Kai Rohrbacher @ 2:2476/451.7, 14.12.94
leicht bearbeitet

Erstellt von Ralf Wiebicke, letzte Änderung 29.01.97