4 Burrows-Wheeler: Difference between revisions
No edit summary |
No edit summary |
||
| Line 15: | Line 15: | ||
Die Sequenz wird cyklisch um eine Stelle verschoben, bis die ursprüngliche Sequenz wieder erreicht ist.<br> | Die Sequenz wird cyklisch um eine Stelle verschoben, bis die ursprüngliche Sequenz wieder erreicht ist.<br> | ||
[[File:BWT.png|thumb|center|Cyklische Rotation]] | [[File:BWT.png|thumb|center|Cyklische Rotation]] | ||
In rot ist | In rot ist der 'Suffix-Array' dargestellt. | ||
'''2. Sortierung'''<br> | '''2. Sortierung'''<br> | ||
| Line 26: | Line 26: | ||
* Hat die gleiche Länge, wie die Originalsequenz <br> | * Hat die gleiche Länge, wie die Originalsequenz <br> | ||
* Originalsequenz T kann direkt aus BWT regeneriert werden | * Originalsequenz T kann direkt aus BWT regeneriert werden | ||
'''3. 'Last-First Zuordnung'''' <br> | |||
Die 'i'te Position des Buchstaben x in der letzten Spalte (Transformation) entspricht der 'i'ten Position in der 1. Spalte<br> | Die 'i'te Position des Buchstaben x in der letzten Spalte (Transformation) entspricht der 'i'ten Position in der 1. Spalte<br> | ||
| Line 38: | Line 38: | ||
'''4. Suche nach einer Sequenz in T''' <br> | '''4. Suche nach einer Sequenz in T''' <br> | ||
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. <br> | 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. <br> | ||
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 | 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. | ||
[[File:Suche.png|thumb|center|Suche einer Sequenz]] | [[File:Suche.png|thumb|center|Suche einer Sequenz]] | ||
Das nächste gesuchte Zeichen ist ein 'A', beide Zeichen des Intervalls stimmen damit überein | 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. | ||
[[File:Suche2.png|thumb|center|Suche einer Sequenz]] | [[File:Suche2.png|thumb|center|Suche einer Sequenz]] | ||
Das 'A' ist das 1. 'A' in dieser Spalte, also wird wieder das entsprechende 'A' in der ersten Spalte gesucht, da das Zeichen in der entsprechenden Zeile nicht mehr mit der gesuchten Sequenz übereinstimmt, ist die Suche an dieser Stelle beendet. | Das 'A' ist das 1. 'A' in dieser Spalte, also wird wieder das entsprechende 'A' in der ersten Spalte gesucht, da das Zeichen in der entsprechenden Zeile nicht mehr mit der gesuchten Sequenz übereinstimmt, ist die Suche an dieser Stelle beendet. | ||
Revision as of 01:37, 16 May 2019
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 der '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.
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.
Das 'A' ist das 1. 'A' in dieser Spalte, also wird wieder das entsprechende 'A' in der ersten Spalte gesucht, da das Zeichen in der entsprechenden Zeile nicht mehr mit der gesuchten Sequenz übereinstimmt, ist die Suche an dieser Stelle beendet.
Der Suffix-Array an dieser Position ist '2'. Zu diesem wird der Wert 1 zugezählt und ergibt somit 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 effiktive Suche nach einem lokalen Alignment.
