3 Alignments

Sequenzalignment

Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können.
Es gibt enorm viele Möglichkeiten eine Sequenz an eine andere zu alignen. Deshalb benötigt man speziell Algorithmen, die die besten Möglichkeiten finden. Um zu bestimmen welches Alignment das beste ist, wird ein Bewertungsschema, der sogenannte Score, angewandt. So kann die Übereinstimmung zweier Sequenzen miteinander quantitativ (mit Zahlen) verglichen werden.
Es werden nicht alle möglichen Alignements ausprobiert und dann deren Scores verglichen, um herauszufinden welches Alignment das beste ist. Mit dieser "brute force" Methode ergeben sich bei kurzen Sequenzen von 100 Basen schon 10⁷⁵ Alignmentmögichkeiten. Stattdessen werden Sequenzen mit Hilfe des "Dynamic Programming" alignet. Es folgt dem Prinzip von "divide and conquer", also die Zerlegung des Problems in viele Unterprobleme, die nacheinander gelöst werden. Zudem ermöglicht das Sequenzalignment die Erkennung ähnlicher Domänen. Da oft sogar homologe Sequenzen, die von einer gemeinsamen Sequenz abstammen, durch indels, die im Laufe der Zeit aufgetreten sind, unterschiedliche Längen besitzen, ist es notwendig gaps Einzufügen um die Ähnlichkeit der beiden Sequenzen sichtbar zu machen (s. Smith-Waterman). Anwenndungen finden Alignments im Sequenzvergeleich, z.B. bei phylogenetischen Untersuchungen.

Man unterscheidet zwei verschiedenen Arten beim Sequenzalignment:

Globales Alignment

• Alignment zwischen zwei Sequenzen, die ähnlich lang sind und bei denen starke Sequenzhomologien erwartet werden
• Vergleich von Gesamtsequenzen
• alle Symbole werden berücksichtigt
• zur Berechnung des optimalen Alignment Scores wird häufig der Needle-Wunsch Algorithmus benutzt

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
• z.B. die 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

Das Alignment beginnt bei dem höchsten erzielten Score in der Matrix

Score: Match: +3 | Mismatch: 0 | Gap: -1