Neue Puzzlestrategie

News: Neue Puzzlestrategie

Es war ein ehrgeiziges Vorhaben, das menschliche Genom zu entziffern. Schließlich war die Datenmenge, die es zu vergleichen und einzuordnen galt, schier unermesslich. So kommt es, bedingt durch die verwendeten Methoden, dass die Karte unseres Erbgutes noch einige weiße Flecken aufweist. Vielleicht kann in Zukunft ein neues Verfahren, das Wissenschaftler nun veröffentlichten, dabei helfen, die Basenabfolge besser zusammenzusetzen.

Thorsten Krome

Am 12. Februar 2001 war es soweit: Zeitgleich erschien in Science und Nature eine Karte der menschlichen Erbinformation – das Ergebnis von gut 15 Jahren Forschungsarbeit. Allerdings spiegelt diese Sequenz von Basenpaaren auch nicht das komplette menschliche Erbgut wider; einige, wenn auch kleine Lücken blieben.

Das Problem liegt in der Methode, mit der das Genom kartiert wurde. So wählte die Firma Celera Genomics einen recht brachialen Ansatz: Wahllos wurden unterschiedlich große Bruchstücke aus dem Genom herausgerissen und deren Sequenz analysiert (whole genome shotgun approach). Im Anschluss mussten die Forscher diese Fragmente der richtigen Stelle im Genom zuordnen – kein leichtes Unterfangen, bedenkt man, dass rund 27 Millionen Sequenzen zusammenzufügen waren. Auch wenn das öffentliche Human Genome Project einen etwas genaueren Ansatz wählte, das Hauptproblem blieb: ein Puzzle aus Abermillionen von Teilen.

Dies zu lösen, ist unter anderem deshalb so schwer, weil das große Genom höherer Organismen aus vielen gleichartigen, sich wiederholenden Teilen besteht. Da lässt sich nur mühsam entscheiden, ob man nun ein neues Bruchstück der Sequenz betrachtet, oder ein bereits bekanntes. "Man muss sich wirklich jede einzelne Base anschauen", erklärt der Computerwissenschaftler Mihai Pop vom Institute for Genomic Research in Rockville.

Das Puzzle-Problem der Genetiker ist dabei analog zu einer altbekannten Optimierungsaufgabe der Mathematik: das Problem des Handlungsreisenden. Bei dieser Aufgabe gilt es, die kürzeste Route zu finden, die eine Reihe von Städten miteinander verbindet, wobei aber jede Stadt nur einmal besucht werden darf. Mathematiker bezeichnen dies auch als Hamilton-Pfad. Das Haarige an dieser Aufgabe ist, dass zur Lösung jede denkbare Möglichkeit durchgespielt werden muss. Das erfordert erhebliche Computerleistung, vor allem deshalb, weil die Anzahl der Möglichkeiten exponentiell von der Zahl der Städte abhängt.

Pavel Pevzner von der University of California in San Diego und seine Kollegen haben nun einen Weg gefunden, das Problem zu entschärfen. Dazu muss das Genom lediglich in kleine, gleich große Bruchstücke zerhackt werden. Aus dem Hamilton-Pfad wird auf diese Weise ein so genannter Euler-Pfad, und der ist ungleich einfacher zu lösen.

Statt jede Stadt nur einmal zu besuchen, darf im Bild des Handlungsreisenden, jetzt nur jeder Weg auf der Suche nach der kürzesten Route einmal beschritten – jeder Knotenpunkt beziehungsweise jede Stadt aber beliebig häufig passiert werden. Diese Aufgabe bezeichnen Mathematiker auch als Problem des chinesischen Briefträgers. Ein Beispiel für ein derartiges Netzwerk ist das "Haus des Nikolaus", ein Gebäude mit fünf Eckpunkten, das sich in einem Zug zeichnen lässt.

"Niemand kann das Problem des Handlungsreisenden lösen, sodass Programme gezwungen sind, willkürliche Annahmen zu treffen, was unweigerlich zu Fehlern führt", erklärt Pevzner. "Der Euler-Pfad nutzt fast dieselbe Formulierung, aber es gibt einen großen Unterschied in der Komplexität." So durfte denn auch Pevzners Programm EULER gegen PHRAP des Human Genome Project antreten, und wie sich zeigte, konnte es fehlerlos die Fragmente von Neisseria meningitidis zusammensetzen, dem Erreger der Hirnhautentzündung.

Wenn auch das Genom dieses Bakteriums noch vergleichsweise einfach aufgebaut ist und es nicht die sich ständig wiederholenden Sequenzen höherer Organismen besitzt, so scheint dieses Ergebnis schon recht vielversprechend. Pop meint deshalb, es wäre noch zu früh, um zu entscheiden, ob EULER weniger Fehler macht als andere Programme. "Ich würde das Programm gerne mit ein paar Genomen testen, die wir hier haben."

Wie auch immer dieser Test ausfallen wird, Pevzner gibt sich optimistisch, dass die Technik auch über die Genkartierung hinaus Anwendung finden wird: "Die Menschen wollen seit 20 Jahren diese Fragmente zusammensetzen, aber eigentlich ist das Problem, ein Puzzle zu lösen, Tausende von Jahren alt. Wir haben nun einen neuen Weg gefunden, Puzzle zu lösen."