4.Burrows-Wheeler: Difference between revisions
No edit summary |
|||
| Line 5: | Line 5: | ||
'''a''': Wofür wird der Burrows-Wheeler Algorithmus verwendet? Welche Funktion besitzt | '''a''': Wofür wird der Burrows-Wheeler Algorithmus verwendet? Welche Funktion besitzt | ||
er? | er? | ||
*Ursprünglich zur Datenkompression entwickelt: In der Transformation ergeben sich längere Abschnitte sich wiederholender Symbole, was Kompression ermöglicht | |||
*Teilstringsuche kann in der Transformation durchgeführt werden. | |||
In der Bioinformatik | *In der Bioinformatik -> read mapping nach sequenzing | ||
*Sortieren ist ohne Informationsverlust möglich: Rücktransformation möglich | |||
| Line 18: | Line 17: | ||
Schritte: | '''Schritte:''' | ||
1. Generiere alle zyklischen Verschiebungen der Template Sequenz T | |||
2. Sortiere die Verschiebungen alphabetisch | |||
3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix | |||
| Line 72: | Line 71: | ||
finden wollen? | finden wollen? | ||
Für diese Anwendung benötigt man die Zahlenwerte, die man den Verschiebungen am Anfang gegeben hat. Man schaut in der 1. Spalte nach dem Intervall mit dem letzten Buchstaben der gesuchten Sequenz, geht damit dann zum entsprechenden Intervall rechts in der letzten Zeile und verkleinert es an den Enden die nicht der Sequenz entsprechen | Für diese Anwendung benötigt man die Zahlenwerte, die man den Verschiebungen am Anfang gegeben hat. Man schaut in der 1. Spalte nach dem Intervall mit dem letzten Buchstaben der gesuchten Sequenz, geht damit dann zum entsprechenden Intervall rechts in der letzten Zeile und verkleinert es an den Enden die nicht der Sequenz entsprechen. | ||
[[File:U4A1d1.PNG|thumb | [[File:U4A1d1.PNG|thumb]] | ||
Im ersten Schritt sehen wir, dass wir ein Zweierintervall haben für C, wenn wir das nach Rechts verfolgen, sehen wir dass die untere Position nicht die gewünschte zweite Position besitzt. Deshalb wird das Intervall unter verkleinert. | Im ersten Schritt sehen wir, dass wir ein Zweierintervall haben für C, wenn wir das nach Rechts verfolgen, sehen wir dass die untere Position nicht die gewünschte zweite Position besitzt. Deshalb wird das Intervall unter verkleinert. | ||
[[File: | [[File:Alignment4.png|thumb]] | ||
Der Rest ist aufgrund der Tatsache, dass die Intervallsgröße nur noch 1 ist, relativ einfach. Dabei wird lediglich die Sequenz weiter rückwärts durchlaufen bis man auf den ersten Buchstaben der gesuchten Sequenz trifft. Die zugehörige Nummer entspricht dem Startpunkt der gesuchten Sequenz. Die Sequenz fängt in String Nummer 4 an. | |||
Der Rest ist aufgrund der Tatsache, dass die Intervallsgröße nur noch 1 ist, relativ einfach. Dabei wird lediglich die Sequenz weiter rückwärts durchlaufen bis man | [[File:Alignment5.png|thumb]] | ||
Latest revision as of 19:29, 31 January 2021
Aufgabe 1
a: Wofür wird der Burrows-Wheeler Algorithmus verwendet? Welche Funktion besitzt er?
- Ursprünglich zur Datenkompression entwickelt: In der Transformation ergeben sich längere Abschnitte sich wiederholender Symbole, was Kompression ermöglicht
- Teilstringsuche kann in der Transformation durchgeführt werden.
- In der Bioinformatik -> read mapping nach sequenzing
- Sortieren ist ohne Informationsverlust möglich: Rücktransformation möglich
b: Nennen Sie die Schritte, welche für eine Burrows-Wheeler Transformation
durchgeführt werden müssen und zeigen Sie dies an folgender Sequenz:
AGTGCCATG$.
Wie lautet der Index dieser Transformation?
Schritte:
1. Generiere alle zyklischen Verschiebungen der Template Sequenz T
2. Sortiere die Verschiebungen alphabetisch
3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix
Zuerst werden alle cyclischen Verschiebungen der Sequenz aufgeschrieben und
nummeriert sie :
$AGTGCCATG 9 G$AGTGCCAT 8 TG$AGTGCCA 7 ATG$AGTGCC 6 CATG$AGTGC 5 CCATG$AGTG 4 GCCATG$AGT 3 TGCCATG$AG 2 GTGCCATG$A 1 AGTGCCATG$ 0
Die Sequenzen werden anschließend alphabetisch geordnet, wobei $ noch vor A kommt
$AGTGCCATG 9 AGTGCCATG$ 0 ATG$AGTGCC 6 CATG$AGTGC 5 CCATG$AGTG 4 G$AGTGCCAT 8 GCCATG$AGT 3 GTGCCATG$A 1 TG$AGTGCCA 7 TGCCATG$AG 2
Die letzte Spalte ist das Ergebnis der Burrows Wheeler Transformation
BWT(T)= G$CCGTTAAG
c: Führen Sie nun eine Rücktransformation der transformierten Sequenz (aus Teil b) mithilfe der „last first“ Zuordnung durch. Beschreiben Sie ihr Vorgehen anhand der einzelnen Teilschritte.
Man sortiert das Ergebnis der BWT alphabetisch um die erste Spalte der Sequenzen zu erhalten und stellt sie der BWT gegenüber. Man weiß, dass der erste Buchstabe in der Burrows-Wheeler-Transformation, der letzte Buchstabe in der Sequenz ist (vor dem $). Außerdem kann man durch die Last-First Zuordnung den Rest der Sequenz bestimmen, denn die Buchstaben in der 1 in der 1. Spalte entspricht dem ersten A in der letzten. Da man weiß, dass in allen anderen Zeilen in der richtigen Sequenz der erste Buchstabe dem letzten Buchstaben folgt, kann man die Sequenz problemlos von hinten an rekonstruieren.
Sequenz: AGTGCCATG$
d: Wie gehen Sie vor, wenn Sie die Teilsequenz GCC in der gegebenen Sequenz finden wollen?
Für diese Anwendung benötigt man die Zahlenwerte, die man den Verschiebungen am Anfang gegeben hat. Man schaut in der 1. Spalte nach dem Intervall mit dem letzten Buchstaben der gesuchten Sequenz, geht damit dann zum entsprechenden Intervall rechts in der letzten Zeile und verkleinert es an den Enden die nicht der Sequenz entsprechen.
Im ersten Schritt sehen wir, dass wir ein Zweierintervall haben für C, wenn wir das nach Rechts verfolgen, sehen wir dass die untere Position nicht die gewünschte zweite Position besitzt. Deshalb wird das Intervall unter verkleinert.
Der Rest ist aufgrund der Tatsache, dass die Intervallsgröße nur noch 1 ist, relativ einfach. Dabei wird lediglich die Sequenz weiter rückwärts durchlaufen bis man auf den ersten Buchstaben der gesuchten Sequenz trifft. Die zugehörige Nummer entspricht dem Startpunkt der gesuchten Sequenz. Die Sequenz fängt in String Nummer 4 an.
