3 Alignments

Auf dieser Seite sind die Themen zusammengeführt, die in Vorlesung 3 am 25.04.2019 behandelt wurden.

Alignments

→ Für ein Alignment werden spezielle Algorithmen benötigt.


Sequenz Alignments

• Ähnlichkeit quantitativ bestimmbar
• Erkennung ähnlicher Domänen
• erfordert das Einfügen von "gaps"

Globales Alignment

• alle Symbole werden berücksichtigt
• Vergleich ähnlicher Sequenzen mit ähnlicher Länge

Beispiel:

H	A	U	S		K	L	A	U	S
↓
H	-	A	U	S		-	H	A	U	S
K	L	A	U	S		K	L	A	U	S
Score 8						Score 8

Bewertungsschema: S_(a,b)={3 a=b match ;0 a≠b mismatch

gaps:	S(a,-)=-1 Deletion
	S(-,b)=-1 Insertion

Lokales Alignment

• Alignment von Teilsequenzen
• Vergleich zweier sehr unterschiedlicher Sequenzen, die aber gleiche Motive besitzen
• Suche einer Gensequenz im Genom

Beispiel:

A	T	G	C	A	T	T	A	C
			C	T	T	T	A

Smith-Waterman Algorithmus

Dynamic programming: "divide and conquer", Aufteilen des Problems in Subprobleme

M_0,0=0
M_0,j=0
M_k,0=0
M_k,j=max(0, M_k-1,j+gp,M_k,j-1+gp,M_k-1,j-1+equal(k,j))