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.