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
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 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 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.
Alignment
Die Eigenschaften der Burrows-Wheeler Transformation erlauben es, eine Sequenz in der Originalsequenz zu suchen, das heißt ein Alginment durchzuführen, obwohl nur die BWT bekannt ist.
In diesem Beispiel wird nach der Sequenz 'ACTA' in der Originalsequenz gesucht. Da nur die BWT gegeben ist, wird zuerst die erste Spalte durch alphabetische Sortierung generiert. Daraus kann wieder die Originalsequenz mit den Indexzahlen generiert werden.
Um das Alignemnt durchzuführen, suchen wir den letzten Buchstabe der zu alignenden Sequenz "ACTA", in der ersten Spalte. In unserem Bespiel, finden wir drei "A". Weil in der gesuchten Sequenz vor "A" ein "T" kommt und der letzte Buchstabe der Zeile, immer der vorangegangene Buchstabe in der Originalsequenz ist, verfolgt man die beiden Zeilen, die ein "T" am Ende besitzen (hier also die ersten beiden Zeilen, die mit einem A beginnen). Dann sucht man die Zeilen, die mit einem "T" beginnen und ein "C" am Ende der Zeile haben. So geht man die gesamte gesuchte Sequenz durch.
Der Suffix-Array an dieser letzten Position ist '6'. Demzufolge beginnt die gesuchte Sequenz an der 6.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.
