# Physikalische Kartierung

Physikalische Kartierung beschreibt die Methode, bei der durch korrekte Anordnung von Klonen aus einem clone-by-clone-shotgun Verfahren die Sequenz eines Chromosoms erlangt werden kann. Durch neue Methoden der Bioinformatik hat sich die Geschwindigkeit der Genkartierung in den letzten Jahren vervielfacht.

## Problemstellung

Das Ziel der physikalischen Kartierung ist es, eine vollständige Sequenz eines Genoms zu erstellen. Bei der Sequenzierung von Chromosomen ergeben sich bestimmte Probleme, die dazu führen, dass nur Abschnitte mit einer Größe von ca. 800 bp am Stück sequenziert werden können. Eine Möglichkeit, dieses Problem zu lösen, ist es, die Sequenzschnipsel anhand zusätzlicher Informationen in eine korrekte Reihenfolge und Anordnung zu bringen, und so aus ihrer Gesamtheit ein komplettes Chromosom zu erhalten.

## Biologischer Hintergrund

Um überhaupt die Möglichkeit zu haben, die Reihenfolge der Klone (Klone bezeichnet in diesem Zusammenhang kleine DNA-Sequenzen; Klone deshalb, weil sie partielle Kopien des Chromosoms sind) festzustellen, müssen sich die Klone überlappen, und durch Sonden muss feststellbar sein, ob und welche Klone sich überlappen. Um genug Klone zu erhalten, wird das Chromosom vervielfältigt und mit Restriktionsenzymen geschnitten, was, je nach Methode, zum partial-digest-problem, oder zum double-digest-problem führt. Vor der Sequenzierung der Klone wird durch Klon-Sonden-Hybridisierung festgestellt, welche Klone mit welchen Sonden hybridisieren. Da die Sonden so gewählt werden, dass sie (im Idealfall) nur einmal im Chromosom vorkommen, kann mit deren Hilfe eine Klon-Sonden-Hybridisierungsmatrix erstellt werden, mit deren Hilfe die Überlappung und Anordnung der Klone festgestellt werden kann. Weiß man wie die Klone sich überlappen, müssen evtl. nicht alle sequenziert werden.

## Der fehlerfreie Fall

Unter der Annahme, dass alle Klone
* die gleiche Länge haben
* alle Überlapps eindeutig sind (jede Sonde bindet nur an einer Stelle) und
* alle Hybridisierungen echte Überlappungen bezeugen
was bedeutet, dass keine Hybridisierung an der falschen Stelle bindet, sodass es wie eine Überlappung aussieht wo keine ist, kann die Reihenfolge der Klone eindeutig mit einem PQ-Baum erstellt werden, bzw. durch Lösung des consecutive-ones-problem.
Die Klon-Sonden-Hybridisierungsmatrix ist eine zweidimensionale Matrix, deren Zeilen für je einen Klon pro Zeile, jede Spalte für eine Sonde pro Spalte stehen. Die Felder der Matrix werden mit 1 beschriftet, falls die jeweilige Sonde mit dem jeweiligen Klon hybridisiert, ansonsten mit 0.
| Klon | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 1 | 1 | 0 | 1 | 0 |
| 3 | 1 | 1 | 0 | 0 | 1 | 0 |
| 4 | 0 | 1 | 1 | 0 | 0 | 1 |
Gesucht ist nun also eine Ordnung der Spalten dieser Matrix M, so dass in jeder Zeile genau ein zusammenhängender Block von Einsen steht. Einen solchen Block nennt man konsekutiv. Ein solcher Block zeigt dann an, welche Sonden nebeneinander auf einem Klon liegen. Klone, die zum Teil mit den gleichen Sonden hybridisieren überlappen, ihre nichtüberlappenden Teile liegen links und rechts neben den Überlapps.
Der zur Lösung dieses Problems wird die Matrix in eine Datenstruktur, die als PQ-Baum bezeichnet wird, umgewandelt.