3 Alignments: Difference between revisions
From Bioinformatik Wiki
| Line 1: | Line 1: | ||
= Alignments = | = Alignments = | ||
Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können. | |||
→ Für ein Alignment werden spezielle Algorithmen benötigt. | → Für ein Alignment werden spezielle Algorithmen benötigt. | ||
<br> | <br> | ||
<br> | <br> | ||
| Line 9: | Line 10: | ||
* Erkennung ähnlicher Domänen | * Erkennung ähnlicher Domänen | ||
* erfordert das Einfügen von "gaps" | * erfordert das Einfügen von "gaps" | ||
== Globales Alignment == | == Globales Alignment == | ||
* Ausrichtung auf die gleiche Länge | * Ausrichtung auf die gleiche Länge | ||
| Line 25: | Line 26: | ||
| H|| -|| A|| U|| S|| || -|| H|| A|| U|| S | | H|| -|| A|| U|| S|| || -|| H|| A|| U|| S | ||
|- | |- | ||
| K|| L || A|| U|| S|| || K|| L|| A|| U|| S | | K|| L || A|| U|| S|| || K|| L|| A|| U|| S | ||
|- | |- | ||
| colspan="5"| Score 8|| || colspan="5"| Score 8 | | colspan="5"| Score 8|| || colspan="5"| Score 8 | ||
|} | |} </big> | ||
<br> | <br> | ||
Bewertungsschema: | Bewertungsschema: | ||
| Line 39: | Line 41: | ||
| || S<sub>(-,b)</sub>=-1 Insertion | | || S<sub>(-,b)</sub>=-1 Insertion | ||
|} | |} | ||
== Lokales Alignment == | == Lokales Alignment == | ||
| Line 45: | Line 46: | ||
* Vergleich zweier sehr unterschiedlicher Sequenzen, die aber gleiche Motive besitzen | * Vergleich zweier sehr unterschiedlicher Sequenzen, die aber gleiche Motive besitzen | ||
*Suche einer Gensequenz im Genom | *Suche einer Gensequenz im Genom | ||
<br> | <br> | ||
Beispiel:<br> | Beispiel:<br> | ||
Revision as of 10:53, 31 January 2021
Alignments
Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können.
→ 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
- Ausrichtung auf die gleiche Länge
- 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
M0,0=0
M0,j=0
Mk,0=0
Mk,j=max(0, Mk-1,j+gp,Mk,j-1+gp,Mk-1,j-1+equal(k,j))
