4.Burrows-Wheeler

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.

Pfad der Rücktransformation

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.