Physical-Mapping

Wir nehmen nun an, daß das vorliegende DNA-Moleküle sehr lang ist, zum Beispiel ein menschliches Chromosom. Eine direkte Sequenzierung mit Hilfe der bekannten Techniken ist bei dieser Größenordnung nicht möglich. Der erste Schritt bei der Erforschung eines solch langen DNA-Moleküls ist die Erstellung einer Karte des Moleküls, die die Position gewisser Marker (z.B. gewisser Gene) auf dem Molekül und die Abstände zwischen diesen Markern angibt. Die Abstände werden hierbei durch die Zahl der Basenpaare zwischen den Markern angegeben. Verfügt man über eine solche Karte (Physical-Map), so kann man nach und nach die Teilsequenzen zwischen den Markern sequenzieren und untersuchen, bis man schließlich die Sequenz des gesamten Moleküls bzw. Chromosomes kennt. Wie beschäftigen uns in diesem Abschnitt mit der sogenannten STS-Verfahren (Sequence-Tagged-Site), das sehr oft in der Praxis eingesetzt wird. Eine Sequence-Tagged-Site  ist eine Sequenz der Länge 200 bis 300 Basenpaare, deren Anfangs- und Endsequenz (Länge 20-30 bp) nur genau einmal auf dem Chromosom vorkommen. Die Anfangs- und Endsequenzen von diesen Markern sind also ``eindeutige'' Primersequenzen. Starten wir also einen PCR-Test für eine beliebige Teilsequenz des Chromosomes, einen sogenannten Clone, mit der Anfangs- oder Endsequenz des Markers als Primer, so setzt nur dann eine Reaktion ein, wenn der Clone den Marker enthält.

Wir betrachten nun das folgende Problem: Gegeben eine Zahl n von Clones des Chromosoms und eine Zahl m von Markern. Bestimme die Reihenfolge der Marker auf dem Chromosom. Kennt man die Reihenfolge, so kann man mit Hilfe spezifischer Experimente die Abstände zwischen den Markern bestimmen. In einer ersten Serie von chemischen Experimenten (PCR-Tests) bestimmen wir zunächst, welcher Clone welche Marker enthält. Hierfür führen wir PCR-Tests mit jedem Clone und der Anfangs- und Endsequenz (Primersequenzen) aller Marker durch. Das Resultat aller Experimente können wir in Form einer Matrix zusammenfassen (siehe Abb. 3.4).

  

Abbildung: Die obige Abbildung zeigt modelhaft ein Chromosom, drei Clones sowie sieben Marker. Die linke Matrix repräsentiert eine mögliche Eingabe für das Physical-Mapping-Problem. Die Reihenfolge der Marker ist nicht bekannt und soll berechnet werden, d.h., die Spalten sollen so permutiert werden, daß ihre Reihenfolge der Ordung der Marker entlang des Chromosomes entspricht. Die rechte Matrix zeigt das Resultat der Berechnungen.

Die Spalten der Matrix repräsentieren die Marker. Die Zeilen repräsentieren die Clones. Falls ein Marker in einem Clone enthalten ist, steht in der entspechenden Matrixkomponente eine 1 andernfalls eine 0. In dieser Matrix ist die Reihenfolge der Spalten (Marker) beliebig. Es gilt nun, die Spalten so zu sortieren (permutieren), daß die Reihenfolge der Matrixspalten der Reihenfolge der Marker auf dem Chromosom entspricht. Falls die Eingabe fehlerfrei ist, gilt die folgende Aussage: Die Spalten liegen genau dann in der richtigen Reihenfolge vor, wenn die Matrix die Consecutive-Ones-Property besitzt, d.h., in jeder Zeile bilden die Einsen der Matrix einen zusammenhängenden Block (siehe Abb. 3.4). In diesem Fall können wir die Ordnung der Marker mit Hilfe eines Algorithmus zur Berechnung einer Spaltenpermutation mit der Consecutive-Ones-Property berechnen. Booth und Luecker haben 1976 einen Algorithmus mit Laufzeit O(m) vorgestellt (siehe [BL76]).

In der Regel sind die Daten jedoch nicht fehlerfrei. Wir werden nun ein Verfahren kennenlernen, das in der Praxis eingesetzt wird. Wir transformieren unser Sortierproblem in ein Graphenproblem. Jeder Knoten des Graphen repräsentiert eine Spalte der Matrix. Zwei Knoten v_i, v_j sind über eine Kante e_ij miteinander verbunden. Das Gewicht der Kante e_ij ist gleich der Hamming-Distanz der von v_i und v_j repräsentierten Spalten. Eine kleine Hamming-Distanz bedeutet, daß die entsprechenden Spalten sehr ähnlich sind und daher in der zu bestimmenden Reihenfolge der Spalten nicht weit voneinander entfernt sein sollten. Man veranschauliche sich hierzu, was es bedeutet, wenn zwei Spalten sich in einer Zeile unterscheiden: Der Clone enthält also einen der beiden Marker und den anderen nicht.

Wir können nun unser Sortierproblem als TSP-Problem (Traveling-Salesman-Problem) definieren: Berechne eine Traveling-Salesman-Tour mit minimalem Gewicht. Das Gewicht einer Tour ist die Summe ihrer Kantengewichte. Eine TSP-Tour besucht jeden Knoten genau einmal. Obwohl das TSP-Problem NP-hard ist, kann man heute Problem-Instanzen mit bis zu 1000 Knoten mit Hilfe von Verfahren der kombinatorischen Optimierung lösen (siehe [JRR97]). Es existiert noch eine Reihe anderer Formulierungen für das Physical-Mapping-Problem (für einen Überblick siehe [Gus97]).