Sequencing-by-Hybridization

Wir werden in diesem Abschnitt ein weiteres Verfahren kennenlernen, das bei der Sequenzierung von DNA-Sequenzen eingesetzt wird. Das Verfahren, das unter dem Namen Sequencing-by-Hybridization (SBH) bekannt ist, basiert auf Hybridisierungs-Experimenten von kurzen Teilstrings einer festen Länge k mit der zu bestimmenden DNA-Sequenz. Das wichtigste Werkzeug des SBH-Verfahrens ist der sogenannte Chip,   eine physikalische Matrix von 4^k Zellen. Jede Zelle enthält Kopien von genau einem der 4^k DNA-Stränge der Länge k. Alle Zellen der Matrix werden dann mit radioaktiv markierten Kopien der zu untersuchenden DNA-Sequenz in Kontakt gebracht. Die DNA-Sequenz hybridisiert dann mit einem DNA-Strang der Länge k, wenn die DNA-Sequenz den Strang als Teilsequenz enthält. Man entfernt dann alle nicht-hybridisierten Kopien der DNA-Sequenz von dem Chip (``Auswaschen''). Die hybridisierten Kopien bleiben in den Zellen an den fixierten DNA-Strängen der Länge k haften. Dann wird ein Film belichtet, der anzeigt, in welchen Zellen eine Hybridisierung stattgefunden hat. Das Ergebnis des ganzen Experiments ist also eine Menge T von k-Tupeln, die als Teilsequenzen in der zu bestimmenden Sequenz auftreten. Mit Hilfe dieser Teilsequenzen versucht man schließlich die gesuchte DNA-Sequenz zu berechnen. Der bekannteste Ansatz für dieses Aufgabenstellung reduziert das Problem auf die Berechnung von Euler-Pfaden in einem Graph.

Wir konstruieren mit Hilfe der Teilsequenzmenge T einen gerichteten Graphen G(T). Die Knoten des Graphen repräsentieren die 4^k-1 DNA-Stränge der Länge k-1. Zwei Knoten v₁ und v₂ werden über eine gerichtete Kante (von v₁ nach v₂) miteinander verbunden, wenn es eine Teilsequenz $t\in T$ mit der folgenden Eigenschaft gibt: Der Präfix der Länge k-1 von t wird durch den Knoten v₁ und der Suffix der Länge k-1 von t wird durch v₂ repräsentiert (siehe Abbildung 3.2). Die Knoten, die keine Kanten besitzen, können entfernt werden.

  

Abbildung: Sei AATTGGCCAT die gesuchte Sequenz. Dann erhalten wir für k=3 die Teilsequenzmenge $T=\{AAT,ATT,TTG,TGG,GGC,GCC,CCA,CAT\}$. Die obige Abbildung zeigt den gerichteten Graphen G(T).

Definition 19   Ein Euler-Pfad  in einem gerichteten Graphen ist ein ``gerichteter Pfad'', der jede Kante des Graphen genau einmal benutzt. Eine Euler-Tour  ist ein Euler-Pfad, der am selben Knoten startet und endet.

Falls die Fragmente fehlerfrei sind und kein Teilstring der Länge k mehrfach in der zu bestimmenden Sequenz vorkommt, dann existiert ein Euler-Pfad, der die gesuchte Sequenz liefert. Die Sequenz startet mit der Sequenz, die der erste Knoten des Pfades repräsentiert. Den Rest der Sequenz erhalten wir, indem wir jeweils den letzten Buchstaben der weiteren Knoten nacheinander hinzufügen. Das Problem die Basensequenz des vorgegebenen DNA-Strangs zu bestimmen, wird also bei diesem Ansatz zu einem Euler-Pfad-Problem reduziert. Da auch diese Formulierung des Sequenzierungs-Problems sehr abstrakt ist, und da das SBH-Verfahren in der Praxis bei der Sequenzierung kaum noch verwendet wird, werden wir uns mit dieser Reduktion im Rahmen der Vorlesung nicht weiter beschäftigen. Pevzner und Lipshutz geben in [PL94] einen Überblick über Sequenzierungs-Verfahren, die auf SBH basieren.