3 Alignments: Difference between revisions
From Bioinformatik Wiki
| Line 64: | Line 64: | ||
M<sub>0,j</sub>=0<br> | M<sub>0,j</sub>=0<br> | ||
M<sub>k,0</sub>=0<br> | M<sub>k,0</sub>=0<br> | ||
[[File:Smith Waterman Algorithmus.jpg|400px| | [[File:Smith Waterman Algorithmus.jpg|400px|frameless]] | ||
Das Alignment beginnt bei dem höchsten erzielten Score in der Matrix | Das Alignment beginnt bei dem höchsten erzielten Score in der Matrix | ||
Score: Match: +3 | Mismatch: 0 | Gap: -1 | Score: Match: +3 | Mismatch: 0 | Gap: -1 | ||
[[File:Smith Waterman.jpg|600px|thumb|left]] | [[File:Smith Waterman.jpg|600px|thumb|left]] | ||
Revision as of 11:34, 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
Das Alignment beginnt bei dem höchsten erzielten Score in der Matrix
Score: Match: +3 | Mismatch: 0 | Gap: -1
