4.Burrows-Wheeler
Aufgabe 1
a: Wofür wird der Burrows-Wheeler Algorithmus verwendet? Welche Funktion besitzt er?
Der BWA wird in der Informatik zur Datenkomprimierung verwendet. In der Transformation ergeben sich längere Abschnitte sich wiederholender Symbole, die Kompression ermöglichen. In der Bioinformatik wird er dazu verwendet um Sequenzabschnitte in großen Sequenzen zu finden. Eine Anwendung wäre zum Beispiel die Position von reads an einem Referenzgenom zu bestimmen. Besonders an der Transformation ist, dass eine Rücktransformation problemlos möglich ist und dass es keinen Informationsverlust bei dem Prozess gibt.
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. Die Zeile an der man am Ende in der linken Zeile endet ist die Position an der die Sequenz beginnt, wenn man +1 hinzufügt.
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 in der sortierten Spalte auf den erste Buchstaben der gesuchten Sequenz trifft. Die zugehörige Nummer (+1, da bei Null angefangen wurde zu nummerieren) entspricht dem Startpunkt der gesuchten Sequenz. Die Sequenz fängt in String Nummer 3 an, also begint die Sequenz an Position 3+1= 4.
