Qi Ouyang, Peter D. Kaplan, Shumao Liu und Albert Libchaber vom NEC-Forschungszentrum in Princeton (New Jersey) haben mit Hilfe von DNA ein Problem der größten Clique gelöst. Die Lösung selbst ist in diesem Falle auch ohne Hilfsmittel leicht zu finden: Der Graph hat nur sechs Knoten, die von 0 bis 5 numeriert sind (rechts), und seine größte Clique besteht offensichtlich aus den Knoten 2, 3, 4 und 5. Bedeutend ist vielmehr der Nachweis, daß ein Problem dieser Klasse im Prinzip auf diesem Wege überhaupt lösbar ist, und zwar mit einer relativ kleinen Anzahl von Aktionen; denn das Problem der größten Clique ist NP-vollständig, gehört also zu der unangenehmen Sorte, für die der Lösungsaufwand exponentiell mit der Problemgröße (hier der Knotenanzahl) ansteigt.

Das Anfangssortiment besteht aus zwölf kurzen DNA-Einzelsträngen, die jeweils in einer großen Anzahl in die Lösung gegeben werden. Jeder Strang besteht aus einem sogenannten Wertsegment (W0 bis W5) flankiert von Positionssegmenten P0 bis P6 und P0 bis P6; ein Querstrich bezeichnet das Komplement, es lagert sich also stets P1 an P1 und so weiter (Bild oben). Einzelheiten zum Aufbau der Stränge finden sich in dem Artikel von Leonard M. Adleman auf Seite 70; im Experiment von Qi und seinen Kollegen haben die Positionssegmente zwanzig statt, wie hier gezeigt, nur acht Anhängsel (Basen).

Zu jedem Wertsegment gibt es zwei Varianten. Eine ist kurz und durch eine spezifische Restriktions-Endonuclease zerschneidbar, die andere lang und nicht zerschneidbar. Die kurzen Varianten symbolisieren eine Eins – der entsprechende Knoten ist in der Teilmenge enthalten –, die langen eine Null – nicht enthalten. Es entstehen also durch Zufallskombination lückenhafte Doppelstränge, in denen die Segmente W0 bis W5 – erzwungen durch die Positionssegmente – stets in der richtigen Reihenfolge aneinandergereiht sind. Bei genügend hoher Anzahl kommen unter ihnen rein durch Zufall alle Kombinationen von Nullen und Einsen vor und damit auch alle Teilmengen der sechs Knoten. Ein Enzym, die DNA-Polymerase, macht die Doppelstränge stabil, indem sie die Lücken füllt.

Die Doppelstränge, die zu – im Sinne der Aufgabenstellung – unzulässigen Teilmengen gehören, werden im Verlauf der Berechnung zerschnitten. Beispielsweise sind alle zu eliminieren, für die sowohl W0=1 als auch W2=1 gilt; denn die Knoten 0 und 2 sind nicht verbunden. In den Doppelsträngen des nebenstehenden Bildes ist das Segment W0 (ganz rechts) weiß gezeichnet, wenn W0=1 ist, schwarz für W0=0; Entsprechendes gilt für W2 (drittes von rechts). Auf die Werte der anderen Segmente kommt es in diesem Moment nicht an.

Man teilt die Gesamtmenge in zwei Teile auf und gibt zu jeder Hälfte eine Restriktions-Endonuklease (durch Scheren symbolisiert), die einen Strang genau dann zerschneidet, wenn W2=1 (links) beziehungsweise W0=1 (rechts) ist. Dabei werden auch Stränge zerschnitten, die eigentlich zulässig sind (etwa links W2=1, W0=0); jedoch bleibt der entsprechende Strang von der jeweils anderen Schere verschont und ist deswegen, wenn man beide Teile wieder zusammenschüttet, in der Lösung noch vertreten. Endgültig eliminiert werden (in diesem Beispiel) nur die Stränge, für die sowohl W0=1 als auch W2=1 gilt – wie gefordert.

Nach dieser Eliminationsphase wird die Polymerase-Kettenreaktion mit den Primern (Anfangssequenzen) P6 und P0 gestartet. Dadurch werden nur unzerschnittene Stränge vervielfältigt. Als einziger bleibt 111100 unzerschnitten, entsprechend der Teilmenge {2,3,4,5}.

Die Numerierung verläuft von rechts nach links – mit gutem Grund. Jede Kette von Nullen und Einsen läßt sich als eine Binärzahl interpretieren. Dabei gibt die Nummer des Kettengliedes – von rechts gezählt und mit 0 beginnend – den Stellenwert der entsprechenden Binärziffer an: Die k-te Ziffer ist mit 2k zu multiplizieren. Demnach kann man das Verfahren von Qi und seinen Kollegen auch als eine Methode auffassen, aus dem vollständigen Sortiment aller Binärzahlen von 0 (000...0) bis 2N-1 (111...1) alle zu streichen, auf die gewisse Bedingungen zutreffen. (In dem beschriebenen Experiment ist N=6.) Beispielsweise eliminiert ein Schritt des Verfahrens alle Teilmengen, die sowohl Knoten 0 als auch Knoten 2 enthalten, denn diese beiden Knoten sind durch eine rote Kante verbunden. In der Binärzahl-Interpretation: Alle Zahlen der Form ***1*1, wobei ein Stern 1 oder 0 bedeutet, werden eliminiert.

Dieser DNA-Computer ist also geeignet, aus einer großen Menge von Zahlen diejenigen ausfindig zu machen, die ein gewisses Kriterium erfüllen – nämlich sämtliche Eliminationsschritte zu überleben. Wenn es also gelingt, eine interessante Eigenschaft – eine Primzahl zu sein, eine gewisse Gleichung zu lösen und so weiter – als Überlebenseigenschaft in diesem Sinne auszudrücken, kann man mit einem DNA-Computer Zahlen mit dieser Eigenschaft finden.


Aus: Spektrum der Wissenschaft 11 / 1998, Seite 21
© Spektrum der Wissenschaft Verlagsgesellschaft mbH