3.Smith-Waterman
Diese Übung war zum Donnerstag, den 02.05.2019 abzugeben.
Aufgabe 1: Definitionen
a.: Definiere die folgenden Begriffe:
- Alignment: Methode, bei der verschiedene Sequenzen optimal aufeinander ausgerichtet werden um übereinstimmende Teile untereinander sichtbar zu machen. Die kann entweder zwischen einem Read und einem Referenzgenom passieren oder zwischen zwei Reads im Zuge der RNAseq.
- Dynamic Programming: Algorithmus zum Lösen von informatischen Problemen. Dabei wird ein Problem in Teilprobleme unterteilt, die nach und nach gelöst und gespeichert werden. Die kann auf Assemblies angewandt werden, indem man die reads nach und nach aneinanderfügt, anstatt dies in einem einzigen Programmschritt durchzuführen. Dabei wird stets ein Paar mit maximalem Match verbunden bevor das nächste Paar verwendet wird.
- lokales Alignment: Alignment von zwei (Teil)-Sequenzen, wird mit dem Smith-Waterman-Algorithmus durchgeführt. Zur Berechnung müssen die Teilsequenzen gefunden werden, die den höchsten Alignmentscore besitzen.
- Gap penalty: Abzug im Alignmentscore, wenn bei einem lokalen Alignment eine Base ungepaart ist (z.B.
AATTGGCC TT-AACCGG |
hätte an Position 3 ein Gap und somit eine Gap penalty.)
- Fasta-Format: textbasiertes Format in dem DNA, RNA und Proteinsequenzen gespeichert werden. Besteht aus 2-3 Zeilen pro Sequenz. die erste Zeile besteht aus einem Header der mit > beginnt und Namen und Beschreibung der Sequenz beinhaltet, danach folgt eine optinale Kommentarzeile, gefolgt von der Zeile mit der eigentlichen Sequenz. Mehrere Sequenzen können in einer Datei gespeichert werden, wenn man einen neuen Header für jede Sequenz beginnt.
Beispiel:
>Probesequenz_1_20190502_ABC AATTAAGCATAAATAGGCTAGCTAAGCTAGCCA >Probesequenz_2_20190502_ABC GGGATTCGACCGATCGAAGCTTAGCGAACGAGA |
- Algorithmus: Handlungsanweisung zur Lösung eines Problems, besteht aus definierten, sequentiellen Abschnitten.
b.: Welche grundsätzlichen Arten von Alignment gibt es?
Lokales Alignment: Alignment von unterschiedlichen (Teil)-Sequenzen, normalerweise unter der Verwendung des Smith-Waterman-Algorithmuses. Wird mit längeren Teilsequenzen immer aufwändiger.
Globales Alignment: Volle Sequenzen werden miteinander alignt. Wird oftmals mit dem Needleman-Wunsch Algorithmus bearbeitet.
Aufgabe 2
a.: Erkläre welche Funktion der Smith-Waterman-Algorithmus hat und wie er funktioniert.
Der Smith-Waterman Algorithmus wird verwendet um lokale Alignments zu finden.
Berechnet wird es mit folgender Matrix:
- [math]\displaystyle{ S(i,j) = \max \begin{Bmatrix} 0 \\ H(i-1,j-1) + \ s(a_i,b_j) & \text{I} \\ H(i-1,j) + \ s(a_i,eps) & \text{II} \\ H(i,j-1) + \ s(eps,b_j) & \text{III} \end{Bmatrix} }[/math]
Erklärt bedeutet dies, das eine Matrix aufgespannt wird mit der Größe Länge von Sequenz A x Länge der Sequenz B, so repräsentiert jede Zelle in der Matrix eine Kombination von einer Base aus Sequenz A und einer Base aus Sequenz B und kann somit als Match oder Mismatch identifiziert werden. Eine Zahlenbewertung (Score) für Match, Mismatch und Gap muss vorgegeben werden. Für jede Zelle der Matrix wird ein Wert berechnet, angefangen oben links und beendet unten rechts in der Matrix. Der Wert für eine bestimmte Zelle ist der höchste Wert aus den folgenden 4:
- Der höchste Wert für die Zelle links oben diagonal (oder 0 falls dies außerhalb der Matrix liegt) plus den Score der Zelle (Match oder Mismatch).
- Der höchste Wert aus der Zelle links daneben plus den Score für einen Gap.
- Der höchste Wert aus Zelle oberhalb plus den Score für einen Gap.
- Null
Die Matrix wird berechnet bis alle Werte bestimmt sind. Dann wird der höchste Wert der gesamten Matrix gesucht. Von diesem Punkt beginnt das Alignment. Von dort aus wird rückwärts die Sequenz bestimmt indem die Rechnung rückwärts verfolgt wird. Der nächste Sequenzteil ist dann jeweils immer die Zelle von der aus man den höchsten Wert berechnet hat. Sobald man jedoch nach links oder nach oben geht anstatt diagonal zu gehen muss man beachten dass man hierbei ein Gap in das Alignment einbaut und dies auch so aufschreiben muss.
Zuerst berechnet man jede Zelle der Matrix...
...und geht dann vom höchsten Wert rückwärts
