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