Wie funktioniert das Manhattan Grid beim Sequenz-Alignment?

Der Manhattan-Grid-Ansatz beim Sequenzalignment bezieht sich auf die Verwendung eines Gitters, um die Ähnlichkeit zwischen zwei Sequenzen zu bewerten. Hier sind die grundlegenden Schritte, wie dieser Ansatz funktioniert:

1. **Gitterstruktur**: Das Gitter wird erstellt, indem die beiden Sequenzen entlang der Achsen eines Koordinatensystems angeordnet werden. Eine Sequenz wird entlang der x-Achse und die andere entlang der y-Achse dargestellt.

2. **Initialisierung**: Die Zellen im Gitter werden initialisiert, wobei die erste Zeile und die erste Spalte oft mit den Kosten für das Einfügen von Lücken gefüllt werden. Diese Kosten können linear oder affine Kosten sein, je nach dem gewählten Modell.

3. **Füllung des Gitters**: Jede Zelle im Gitter wird mit einem Wert gefüllt, der die Kosten für das Alignment bis zu diesem Punkt darstellt. Die Kosten werden typischerweise durch die Berücksichtigung der folgenden drei Möglichkeiten berechnet:
- **Match/Mismatch**: Wenn die Zeichen in beiden Sequenzen übereinstimmen oder nicht.
- **Insertion**: Wenn ein Zeichen in einer Sequenz eingefügt wird.
- **Deletion**: Wenn ein Zeichen aus einer Sequenz gelöscht wird.

Die Werte in den Zellen werden durch die Wahl der minimalen Kosten aus den benachbarten Zellen (links, oben, diagonal) berechnet.

4. **Rückverfolgung**: Nachdem das Gitter vollständig gefüllt ist, wird der optimale Alignment-Weg durch Rückverfolgung von der letzten Zelle (in der unteren rechten Ecke des Gitters) zur ersten Zelle (in der oberen linken Ecke) ermittelt. Dies geschieht, indem man den Pfad verfolgt, der die minimalen Kosten aufweist.

5. **Ergebnis**: Das Ergebnis ist ein optimales Alignment der beiden Sequenzen, das die minimalen Kosten für das Alignment darstellt.

Der Manhattan-Grid-Ansatz ist besonders nützlich, weil er eine klare visuelle Darstellung der Alignment-Problematik bietet und es ermöglicht, verschiedene Alignment-Strategien zu vergleichen.