Diese eher als Denkmodell zu betrachtende Maschine ist in der ersten Jahrhunderthälfte von dem Mathematiker und Vordenker Alan M. Turing ersonnen worden und sollte ohne Einschränkungen für Berechnungen einsetzbar sein. In einer einfachen Fassung setzt sie sich aus zwei Magnetbändern zusammen und einer endlichen Steuereinheit, die zwischen den Bändern vermittelt. Das erste Band dient als Vorlage für die Steuereinheit und bleibt unverändert. Demgegenüber kann die Einheit das zweite Band ablesen und beschriften. Die Parallelität zwischen Turing-Maschine und DNA-Neusynthese liegt auf der Hand.

Der Informatiker und Biochemiker Leonard M. Adleman hat diese Übereinstimmung 1994 als erster beschrieben. Um zu beweisen, daß man mit der Turing-Maschine aus DNA und Polymerase rechnen kann, hat er sich eines Problems angenommen, das als unterhaltsame Knobelei auf der Rätselseite von Zeitungen bekannt ist: Wie gelangt ein Reisender von Hamburg über Köln und Berlin nach München. Er muß jede Stadt einmal gesehen haben, darf sie aber nicht häufiger bereisen, und manche Routen sind Einbahnstraßen. Für Informatiker stellt dieses Spiel ein ernstzunehmendes Problem dar, zu Ehren des irischen Astronomen W. R. Hamilton sprechen sie vom Problem der Hamiltonschen Wege.

Adleman hat angesetzt, indem er die Städte und Reiserouten jeweils als 8-stellige DNA-Sequenzen kodiert hat. In diesem System steht die Sequenz GTCCATGA z. B. für Hamburg und setzt sich aus den Silben GTCC "nach Hamburg fahren" und ATGA "von Hamburg abreisen" zusammen. Wenn die Sequenz CTAAGTCA für Köln steht, heißt CTAA "nach Köln fahren", und GTCA bedeutet "von Köln abreisen". Verbindet man zwei Silben von verschiedenen Städten miteinander, ergibt sich eine Route. Wer ATGACTAA sagt, fährt von Hamburg nach Köln. Adleman hat für alle Städte und Routen die zugehörigen DNA-Sequenzen und den jeweiligen Gegenstrang hergestellt. Mischt man alle DNA-Sequenzen miteinander, lagern sich unter geeigneten experimentellen Vorgaben die komplementären Stränge aneinander. So finden Strang und Gegenstrang für "Köln" zueinander, aber die "Köln"-Sequenz lagert sich über jeweils vier Positionen auch an die Sequenz "von Köln nach Berlin" und "von Hamburg nach Köln". Wenn das geschieht, sind die Enden frei für weiteres Aneinanderlagern, so lange, bis die Zielstadt ("nach München") erreicht ist. Als Ergebnis liegen alle möglichen Reiserouten als Doppelstränge vor, gleichzeitig und nebeneinander.

Bezogen auf das Problem hielt Adleman damit die richtige Lösung in Händen, auch wenn sie sich noch unter den vielen falschen versteckte. Um das eine Weizenkorn von der vielen Spreu zu trennen, setzte er die modernen molekularbiologischen Methoden ein. Zunächst die Polymerase-Ketten-Reaktion (PCR). Sie ermöglichte ihm, diejenigen Sequenzen zu erkennen und zu vermehren, die wie gewünscht Start und Ziel Hamburg-München aufweisen. Darunter waren aber gleichermaßen Sequenzen wie die Direktverbindung Hamburg-München oder Hamburg-Berlin-München. In den letzten Schritten trennte er also die einzig richtige Lösung vom Rest mit falschen Weg, aber richtigem Start und Ziel. Hybridisierungen sind dafür die Methode der Wahl. Wie die PCR ist dies eine Standardmethode in jedem molekularbiologisch arbeitenden Labor. Sie lassen sich mit molekularen Angeln vergleichen. Man hängt einen speziellen Köder in Form einer DNA-Sequenz an eine Haken, und nur ganz bestimmte Fische, die komplementären Sequenzen, beißen an. Adleman angelte in seinem Teich erst nach der Sequenz für die eine Mittelstadt, Start und Ziel waren ja weiterhin dabei, dann nach der Sequenz, die neben dieser auch die zweite Mittelstadt enthielt – und hatte seine Lösung!

Sein tatsächliches Problem, für das er den DNA-Computer prüfen wollte, war komplizierter. Er suchte eine Reiseverbindung für sieben Städte. Die Lösung fanden er und sein Computer nach einer Woche gemeinsamer experimenteller Arbeit. Zum Vergleich: Tests haben erbracht, daß ein Mensch durchschnittlich knapp eine Minute zum Lösen der Aufgabe braucht. Warum der ganze Aufwand trotzdem lohnt und das Ergebnis ermutigt weiterzumachen, wird erst klar, wenn man sich überlegt, welche Art von Problem aus der Informatik hier vorliegt. Die Hamiltonsche Wege fallen in die Kategorie der sogenannten NP-Probleme. Die Berechnungszeit für ein NP-Problem kann exponentiell mit der Anzahl der Variablen zunehmen und einen Komplexitätsgrad erreichen, der eine Bearbeitung mit konventionellen Rechnern nicht mehr erlaubt. DNA-Computer gehen hier einen grundsätzlich anderen Weg: Sie rechnen parallel. Alle verschiedenen Lösungsmöglichkeiten, hier die einzelnen Reisewege, liegen als DNA-Stränge nebeneinander vor und werden gleichzeitig und nicht nacheinander auf ihre Richtigkeit getestet.

Darüber hinaus sieht Adleman weitere Vorteile: Zum einen speichern DNA-Moleküle ihre Information bedeutend dichter als herkömmliche Datenträger wie beispielsweise CDs. Für die Speicherung einer beliebigen Datenmenge benötigt man entweder viele tausend CDs oder wenige Milligramm DNA. Zum anderen arbeiten DNA-Rechner energetisch effizienter. Gibt man einen bestimmten Energiebetrag vor, erstreckt sich der Unterschied in der notwendigen Rechenleistung über bis zu 10 Zehnerpotenzen.

Adleman hat Pionierarbeit geleistet und ein neues Arbeitsgebiet erschlossen, das auf andere Gruppen ansteckend wirkte, die mit verschiedenen Methoden unterschiedliche Probleme bearbeiteten. Gemeinsam ist jedoch die parallele Informationsverarbeitung und daß die Lösungen als DNA-Stränge kodiert sind. Die genetische Information, falls sie in so kurzen Sequenzen überhaupt vorhanden sein sollte, ist in diesem Zusammenhang ohne Bedeutung. Was zählt, ist der Codierungscharakter und die chemische Eigenschaft, daß komplementäre DNA-Stränge sich aneinander lagern und wieder voneinander lösen lassen.

In Nature vom 13. Januar 2000 berichtet Lloyd Smith mit seinen Kollegen von der University of Wisconsin über die Lösung eines weiteren NP-Problems. Eine SAT-Aufgabe, das härteste NP-Problem überhaupt. Es stammt aus der Logik und arbeitet mit Aussagen, die WAHR oder FALSCH sein können und durch UND oder ODER logisch miteinander verknüpft werden. In der einfachen Form mit wenigen Aussagen und Verknüpfungen bleiben sie noch anschaulich. Ein Beispiel mit vier Aussagen und zwei UND- und ODER-Verknüpfungen könnte lauten: Wir machen eine Wanderung, wenn heute die Sonne scheint ODER wenn es warm ist UND wenn wir heute Sonntag ODER einen Feiertag haben. Die richtige Lösung genügt (SATisfies) allen Bedingungen gleichzeitig. Das spezifische Problem, das die Autoren wählten, war stark formalisiert und bestand aus vier Aussagen, die sie mehrfach mittels UND und ODER verknüpften. Mit n=4 gibt es 2n=16 verschiedene Lösungsmöglichkeiten.

Um zu testen, ob es eine Lösung gibt, die alle Verknüpfungen richtig erfüllt, hat die Gruppe um Smith einen DNA-Chip konstruiert. Zunächst haben die Forscher die ODER-Verknüpfungen der WAHR/FALSCH-Aussagen als Folge binärer Zahlen angegeben. Die Folge 0001 steht für: Aussage 1, 2 und 3 WAHR, Aussage 4 FALSCH. Anschließend haben sie diese Zahlenfolgen in DNA-Sequenzen umgeschrieben, ähnlich wie Adleman seine Städte und Reiserouten als DNAs kodiert hatte.

Smiths Team hat die Teilstücke jedoch zunächst nur als Einzelstränge vorgegeben. Diese bekamen dann an einem Ende einen molekularen Klebstoff und wurden auf eine Goldoberfläche geheftet. Der so entstandene Chip enthielt alle möglichen Lösungen des Problems. Im wesentlichen nutzten auch Smith und seine Kollegen für die folgenden molekularen Rechenschritte die Komplementarität von DNA-Strängen aus. Da jede Lösung für ein Teilproblem bekannt war, konnten sie die Teilantwort als Gegenstrang herstellen und zu dem Chip geben. Die Sequenz findet ihren Partner auf dem Chip und hybridisiert mit ihm zum Doppelstrang. Alle anderen Sequenzen codieren keine Lösung für dieses Problem und bleiben ungepaart. Damit sind sie angreifbarer, denn bestimmte Enzyme der Zelle können Einzelstränge abbauen, während Doppelstränge ungeschoren davonkommen. Die falschen Antworten verschwinden somit, und nur die richtigen sind weiterhin vorhanden. Durch Temperaturerhöhung trennt Smith die Doppelstränge und wäscht die hinzugegebenen Sequenzen wieder ab. Die DNAs liegen daraufhin unverbraucht als Einzelstränge vor, und es erfolgt der zweite Rechenschritt, das zweite Teilproblem bearbeitend: Vorgabe der Lösung als DNA-Einzelstrang, Bindung an den Gegenstrang auf dem Chip, Abbau der falschen DNAs, Regeneration des Chips über Trennung der Doppelstränge. Wieviele Rechenschritte der Computer ausführen muß, hängt von der Anzahl der UND-Verknüpfungen ab. Pro Verknüpfung ein Rechenschritt. Nach dem letzten Schritt haben die Forscher die übriggebliebenen Sequenzen vom Chip gelesen, in den binären WAHR/FALSCH Code umgeschrieben und die Lösung für ihr SAT-Problem erhalten.

Läßt man die Vorarbeiten wie Herstellung der DNAs außer acht, muß man mit einem DNA-Rechner nur (3k+1) Schritte ausführen, wobei k die Anzahl der UND-Verknüpfungen ist, bei k=30 ergeben sich demnach 91 Schritte. Verschwindend wenig, wenn man bedenkt, daß in den Lösungsweg auf herkömmliche Art die Anzahl n der WAHR/FALSCH-Aussagen einfließt und der Rechner für n=50 mehr als 1 Million Schritte braucht.

Diese Verbindung aus Molekularbiologie und Informatik ist noch jung. Daher verwundert es nicht, daß die Wissenschaftler auch mit Problemen ganz anderer Art konfrontiert werden. So stehen den unbestreitbaren Vorzügen auf der Informatik-Seite einige Nachteile biologischer Natur gegenüber. Die Smith-Gruppe sagt selbst, daß während der Hybridisierungsschritte Fehler entstehen können. Nicht jede DNA-Sequenz ist gleichermaßen als Lösungsvorgabe geeignet. Es liegt in ihrer Natur, daß Einzelstränge unterschiedlich schnell ihr Gegenstück finden, daher länger als vorgesehen ungepaart bleiben und fälschlicherweise abgebaut werden. Umgekehrt können manche DNAs sich so falten, daß sie nach außen wie ein Doppelstrang erscheinen und von dem Abbau verschont bleiben. Andere Einzelstränge überleben, weil sie zufällig nicht abgebaut werden. Die Erfolgsquote in Smiths Experimenten lag bei 94 Prozent, immerhin 6 Prozent der falschen Antworten wurden demnach nicht ausgemerzt. Erschwerend kommen die hohen Kosten für die Herstellung der DNA-Moleküle hinzu.

Vor diesem Hintergrund bewerten einzelne Wissenschaftler die Zukunftsaussichten des Systems unterschiedlich. "Es ist völlig absurd, die Zukunft dieser Technologie vorhersehen zu wollen", meinen die Informatiker Mitsunori Ogihara und Animesh Ray. Für sie liegt die ideale Anwendung der biomolekularen Computer nicht so sehr in der Lösung hochkomplexer NP-Probleme. "Vielleicht wird eines Tages ein organischer Computer benötigt, der einem lebenden System eingepflanzt wird und dort eindringende chemische Botschaften oder Signale aus der Außenwelt miteinander verrechnet." Bis es soweit ist, dürfen Sie auf die Frage, was ein Computer ist, weiterhin antworten: "Wie immer, Bildschirm, Tastatur, Prozessor, Festplatte – das Übliche."