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 TTCTAACTA$

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.

Eigenschaften der BWT :

• Hat die gleiche Länge, wie die Originalsequenz
  
• Originalsequenz T kann direkt aus BWT regeneriert werden

Rücktransformation - Last-First Zuordnung

Aus der BWT lässt sich die Originalsequenz rekonstruieren. Die Rekonstruktion folgt dem Prinzip: Die 'i'te Position des Buchstaben x in der letzten Spalte (Transformation) entspricht der 'i'ten Position in der 1. Spalte
Der erste Schritt die die Wiederherstellung der ersten Spalte. Da es sich um die alphabetisch sortierten Sequenzen gehandelt hat, lässt sich die erste Spalte einfach durch eine erneute alphabetische Sortierung der BWT wiederherstellen. Um die Originalsequenz zu erhalten, startet man in der ersten Zeile. Von der ersten Zeile wissen wir, dass es sich um die Originalsequenz handelt (außer, dass das Sonderzeichen vorne steht), d.h. auch der letzte Buchstabe der ersten Zeile entspricht dem letzten Element in der Originalsequenz. Hier mit einem gelben Kästchen markiert. Auch die Indexzahl 9 kann dem Buchstaben zugeordnet werden, da es sich um den letzten Buchstaben handelt. Von dort ausgehend kann das oben genannte Prinzip zur Rekonstruktion angewendet werden. Demnach entspricht die erste Position (es handelt sich um das erste A in der BWT) des Buchstabens "A" in der letzten Spalte, dem ersten "A" in der ersten Spalte. Es handelt sich also um das selbe "A" (gekennzeichnet durch den schwarzen diagonal verlaufenden Pfeil). Demnach ist das A in der ersten Spalte (hier zweite Zeile) die zyklische Verschiebung des A in der letzen Spalte (erste Zeile). Logischerweise ist damit der letzte Buchstabe der zweiten Zeile, der Buchstabe der in der Originalsequenz vor dem "A" kommt. Das "T" kann also vor das "A" geschrieben werden und den Index 8 bekommen, usw.

Rücktransformation

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.