4 Burrows-Wheeler
Auf dieser Seite sind die Themen zusammengeführt, die in Vorlesung 4 am 02.05.2019 behandelt wurden.
Burrows-Wheeler Transformation
Die Burrows-Wheeler Induzierung wurde in der Informatik ursprünglich zur Optimierung von Daten-Kompression entwickelt.
Sie eignet sich auch gut zur effizienten Suche großer Texte und somit zur Suche eines optimalen Alignments.
Vorteile
- Sehr schnell und verbraucht wenig Speicher
- Eine Rücktransformation ist Möglich
- Kein Informationsverlust beim Sortieren
Transformation
Beispiel an der Sequenz T = ACAACG$
1. Generierung aller cyclischen Verschiebungen von T
Die Sequenz wird cyklisch um eine Stelle verschoben, bis die ursprüngliche Sequenz wieder erreicht ist.
In rot ist die 'Suffix-Array' dargestellt.
2. Sortierung
Die cyklische Rotation von 'T' wird alphabetisch sortiert, dabei hat das Sonderzeichen (in diesem Fall $) den niedrigsten Wert.
Die letzte Spalte wird als Burrows-Wheeler Transformation (BWT) bezeichnet.
ACAACG$ → CC$AAAC
Eigenschaften der BWT :
- Hat die gleiche Länge, wie die Originalsequenz
- Originalsequenz T kann direkt aus BWT regeneriert werden
'3. Last-First Zuordnung'
Die 'i'te Position des Buchstaben x in der letzten Spalte (Transformation) entspricht der 'i'ten Position in der 1. Spalte
Benötigt werden nur die erste und letzte Spalte nach der cyklischen Rotation.
Begonnen wird mit dem ersten Zeichen der BWT, in diesem Fall 'G', dieses stellt das letzte Zeichen der Originalsequenz dar. Da es das 1. 'G' in der Spalte ist, wird auch das 1. 'G' in der ersten Spalte gesucht, das entsprehende Zeichen der letzten Spalte in der gleichen Zeile, ist das vorletzte Zeichen der Originalsequenz. In diesem Fall ist es C'.
Da das 'C' das letzte in dieser Spalte ist, wird auch nach dem letzten 'C' in der ersten Spalte gesucht und somit nach dem entsprechenden Zeichen in dieser Zeile. In diesem Fall ist es ein 'A' und dies ist das nächste Zeichen in der Originalsequenz.
Nach diesem Schema wird so lange weiter gearbeitet, bis das Sonderzeichen erreicht und die Originalsequenz rekonstruiert ist.
4. Suche nach einer Sequenz in T
In diesem Beispielt wird nach der Sequenz 'AAC' in der Originalsequenz T gesucht. Dafür werden wieder nur die erste und letzte Spalte der alphabetischen Sortierung benötigt.
