4 Burrows-Wheeler
Burrows-Wheeler Transformation
Die Burrows-Wheeler Transformation 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.
Ein BWT basierender Algorithmus wird zur Assemblierung der “reads” einer RNASeq verwendet.
Vorteile
- Sehr schnell und verbraucht wenig Speicher
- Eine Rücktransformation ist verlustfrei 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 der 'Suffix-Array' dargestellt.
2. Sortierung
Die cyklische Rotation von 'T' wird alphabetisch sortiert, dabei hat das Sonderzeichen (in diesem Fall $) den niedrigsten Wert. (Wird also immer nach vorne gestellt, da es noch vor 1 bzw A kommt)
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
Rücktransformation - 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 zyklischen 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 entsprechende 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.
Alignment
In diesem Beispiel 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.
Begonnen wird mit der Suche des ersten Zeichens der gesuchten Sequenz 'C', in der ersten Spalte. Das Intervall wird auf die letzte Spalte, der gleichen Zeilen übertragen.
Das nächste gesuchte Zeichen ist ein 'A', beide Zeichen des Intervalls stimmen damit überein. Da es das 2. und 3. 'A' in dieser Spalte sind, wird wieder in der ersten Spalte nach den entsprechenden Zeichen gesucht. Das nächste Zeichen der gesuchten Sequenz ist ein 'A', da dieses in den entsprechenden Zeilen nur ein mal vorkommt, wird das Intervall verkleinert und somit so angepasst, dass nur die gesuchten Zeichen darin vorkommen.
Der Suffix-Array an dieser Position ist '3'. Demzufolge beginnt die gesuchte Sequenz an der 3.Position in der Originalsequenz.
Diese Burrows-Wheeler Transformation kann mit jeder beliebigen Sequenz durchgeführt werden und ermöglicht eine effektive Suche nach einem lokalen Alignment.
