4 Burrows-Wheeler - Revision history

Skl: /* Alignment */

2021-09-27T10:57:14Z

Alignment

← Older revision		Revision as of 12:57, 27 September 2021
Line 39:		Line 39:

	=== Alignment ===		=== 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 '~~AAC~~' in der Originalsequenz T gesucht. ~~Dafür werden wieder~~ nur die erste ~~und letzte~~ Spalte ~~der alphabetischen~~ Sortierung ~~benötigt~~. <br>		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. <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 Zeilen übertragen.~~		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.
	~~[[File:Alignment1.png\|thumb\|center]]~~		Der Suffix-Array an dieser letzten Position ist '6'. Demzufolge beginnt die gesuchte Sequenz an der 6.Position in der Originalsequenz.
	~~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:Alignment BWT.png\|thumb\|center]]
	~~[[File:Alignment2~~.~~png\|thumb\|center]]~~

	Der Suffix-Array an dieser Position ist '3'. Demzufolge beginnt die gesuchte Sequenz an der 3.Position in der Originalsequenz.
	[[File:~~Alignment3~~.png\|thumb\|center]]

	Diese Burrows-Wheeler Transformation kann mit jeder beliebigen Sequenz durchgeführt werden und ermöglicht eine effektive Suche nach einem lokalen Alignment.		Diese Burrows-Wheeler Transformation kann mit jeder beliebigen Sequenz durchgeführt werden und ermöglicht eine effektive Suche nach einem lokalen Alignment.

Skl: /* Transformation */

2021-09-27T10:16:14Z

Transformation

← Older revision		Revision as of 12:16, 27 September 2021
Line 22:		Line 22:

	'''2. Sortierung'''<br>		'''2. Sortierung'''<br>
	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)<br>		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)<br>
	[[File:Alphabetische_Sortierung_BWT.png\|thumb\|center]]		[[File:Alphabetische_Sortierung_BWT.png\|thumb\|center]]
	Die letzte Spalte wird als '''Burrows-Wheeler Transformation''' (BWT) bezeichnet.<br>		Die letzte Spalte wird als '''Burrows-Wheeler Transformation''' (BWT) bezeichnet.<br>
Line 29:		Line 29:
	'''Eigenschaften der BWT :'''<br>		'''Eigenschaften der BWT :'''<br>
	* 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 kann direkt aus BWT regeneriert werden

	=== Rücktransformation - Last-First Zuordnung ===		=== Rücktransformation - Last-First Zuordnung ===

Skl: /* Transformation */

2021-09-27T10:15:35Z

Transformation

← Older revision		Revision as of 12:15, 27 September 2021
Line 16:		Line 16:
	Beispiel an der Sequenz TTCTAACTA$<br>		Beispiel an der Sequenz TTCTAACTA$<br>

	'''1. Generierung aller cyclischen Verschiebungen ~~von T~~'''<br>		'''1. Generierung aller cyclischen Verschiebungen '''<br>
	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:Burrows_Wheeler_zyklische_Verschiebung_.png\|thumb\|center]]		[[File:Burrows_Wheeler_zyklische_Verschiebung_.png\|thumb\|center]]

Skl: /* Transformation */

2021-09-27T10:15:16Z

Transformation

← Older revision		Revision as of 12:15, 27 September 2021
Line 14:		Line 14:

	=== Transformation ===		=== Transformation ===
	Beispiel an der Sequenz ~~T = ACAACG~~$<br>		Beispiel an der Sequenz TTCTAACTA$<br>

	'''1. Generierung aller cyclischen Verschiebungen von T'''<br>		'''1. Generierung aller cyclischen Verschiebungen von T'''<br>
Line 25:		Line 25:
	[[File:Alphabetische_Sortierung_BWT.png\|thumb\|center]]		[[File:Alphabetische_Sortierung_BWT.png\|thumb\|center]]
	Die letzte Spalte wird als '''Burrows-Wheeler Transformation''' (BWT) bezeichnet.<br>		Die letzte Spalte wird als '''Burrows-Wheeler Transformation''' (BWT) bezeichnet.<br>
	~~ACAACG$ → CC$AAAC~~<br>		<br>

	'''Eigenschaften der BWT :'''<br>		'''Eigenschaften der BWT :'''<br>

Skl: /* Rücktransformation - Last-First Zuordnung */

2021-09-23T19:01:20Z

Rücktransformation - Last-First Zuordnung

← Older revision		Revision as of 21:01, 23 September 2021
Line 34:		Line 34:
	Aus der BWT lässt sich die Originalsequenz rekonstruieren. Die Rekonstruktion folgt dem Prinzip:		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<br>		Die 'i'te Position des Buchstaben x in der letzten Spalte (Transformation) entspricht der 'i'ten Position in der 1. Spalte<br>
	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.		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.

	[[File:Rücktransformation.png\|200px\|thumb\|center\|Rücktransformation]]		[[File:Rücktransformation.png\|200px\|thumb\|center\|Rücktransformation]]

Skl: /* Rücktransformation - Last-First Zuordnung */

2021-09-23T18:52:57Z

Rücktransformation - Last-First Zuordnung

← Older revision		Revision as of 20:52, 23 September 2021
Line 32:		Line 32:

	=== Rücktransformation - Last-First Zuordnung ===		=== 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<br>
			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.

	~~Die 'i'te Position des Buchstaben x in der letzten Spalte (Transformation) entspricht der 'i'ten Position in der 1. Spalte<br>~~		[[File:Rücktransformation.png\|200px\|thumb\|center\|Rücktransformation]]
	~~Benötigt werden nur die erste und letzte Spalte nach der zyklischen Rotation.<br>~~
	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'.
	[[File:~~Erster_schritt~~.png\|thumb\|center]]
	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.
	~~[[File:2._Schritt.png~~\|~~thumb\|center~~]]
	~~Nach diesem Schema wird so lange weiter gearbeitet, bis das Sonderzeichen erreicht und die Originalsequenz rekonstruiert ist.<br><br>~~

	=== Alignment ===		=== Alignment ===

Skl: /* Transformation */

2021-09-23T18:03:50Z

Transformation

← Older revision		Revision as of 20:03, 23 September 2021
Line 18:		Line 18:
	'''1. Generierung aller cyclischen Verschiebungen von T'''<br>		'''1. Generierung aller cyclischen Verschiebungen von T'''<br>
	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_Rotation~~.png\|thumb\|center]]		[[File:Burrows_Wheeler_zyklische_Verschiebung_.png\|thumb\|center]]
	In rot ist der 'Suffix-Array' dargestellt.		In rot ist der 'Suffix-Array' dargestellt.

	'''2. Sortierung'''<br>		'''2. Sortierung'''<br>
	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)<br>		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)<br>
	[[File:~~Bwt sortierung~~.png\|thumb\|center]]		[[File:Alphabetische_Sortierung_BWT.png\|thumb\|center]]
	Die letzte Spalte wird als '''Burrows-Wheeler Transformation''' (BWT) bezeichnet.<br>		Die letzte Spalte wird als '''Burrows-Wheeler Transformation''' (BWT) bezeichnet.<br>
	ACAACG$ → CC$AAAC<br>		ACAACG$ → CC$AAAC<br>
Line 30:		Line 30:
	* 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

	=== Rücktransformation - Last-First Zuordnung ===		=== Rücktransformation - Last-First Zuordnung ===

Mka: /* Burrows-Wheeler Transformation */

2021-01-31T11:53:37Z

Burrows-Wheeler Transformation

← Older revision		Revision as of 13:53, 31 January 2021
Line 6:		Line 6:
	Ein BWT basierender Algorithmus wird zur Assemblierung der “reads” einer RNASeq verwendet.		Ein BWT basierender Algorithmus wird zur Assemblierung der “reads” einer RNASeq verwendet.
	<br>		<br>


	'''Vorteile'''<br>		'''Vorteile'''<br>
Line 29:		Line 30:
	* 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

			=== Rücktransformation - Last-First Zuordnung ===
	=== Rücktransformation - 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 41:		Line 41:
	Nach diesem Schema wird so lange weiter gearbeitet, bis das Sonderzeichen erreicht und die Originalsequenz rekonstruiert ist.<br><br>		Nach diesem Schema wird so lange weiter gearbeitet, bis das Sonderzeichen erreicht und die Originalsequenz rekonstruiert ist.<br><br>

			=== Alignment ===

	~~=== Alignment === <br>~~
	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. <br>		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. <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 Zeilen übertragen.		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]]		[[File:Alignment1.png\|thumb\|center]]
	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 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]]		[[File:Alignment2.png\|thumb\|center]]

	Der Suffix-Array an dieser Position ist '3'. Demzufolge beginnt die gesuchte Sequenz an der 3. Position in der Originalsequenz.		Der Suffix-Array an dieser Position ist '3'. Demzufolge beginnt die gesuchte Sequenz an der 3.Position in der Originalsequenz.
	[[File:~~Suche4~~.png\|thumb\|center]]		[[File:Alignment3.png\|thumb\|center]]

	Diese Burrows-Wheeler Transformation kann mit jeder beliebigen Sequenz durchgeführt werden und ermöglicht eine effektive Suche nach einem lokalen Alignment.		Diese Burrows-Wheeler Transformation kann mit jeder beliebigen Sequenz durchgeführt werden und ermöglicht eine effektive Suche nach einem lokalen Alignment.

Mka: /* Transformation */

2021-01-31T11:21:57Z

Transformation

← Older revision		Revision as of 13:21, 31 January 2021
Line 14:		Line 14:
	=== Transformation ===		=== Transformation ===
	Beispiel an der Sequenz T = ACAACG$<br>		Beispiel an der Sequenz T = ACAACG$<br>

	'''1. Generierung aller cyclischen Verschiebungen von T'''<br>		'''1. Generierung aller cyclischen Verschiebungen von T'''<br>
	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_Rotation.png\|thumb\|center]]
	In rot ist der 'Suffix-Array' dargestellt.		In rot ist der 'Suffix-Array' dargestellt.

	'''2. Sortierung'''<br>		'''2. Sortierung'''<br>
	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)<br>		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)<br>
	[[File:Bwt sortierung.png\|thumb\|center~~\|Alphabetische Sortierung~~]]		[[File:Bwt sortierung.png\|thumb\|center]]
	Die letzte Spalte wird als '''Burrows-Wheeler Transformation''' (BWT) bezeichnet.<br>		Die letzte Spalte wird als '''Burrows-Wheeler Transformation''' (BWT) bezeichnet.<br>
	ACAACG$ → CC$AAAC~~<br>~~<br>		ACAACG$ → CC$AAAC<br>

	'''Eigenschaften der BWT :'''<br>		'''Eigenschaften der BWT :'''<br>
	* 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>

			=== Rücktransformation - 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>
	Benötigt werden nur die erste und letzte Spalte nach der ~~cyklischen~~ Rotation.<br>		Benötigt werden nur die erste und letzte Spalte nach der zyklischen Rotation.<br>
	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'.		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'.
	[[File:Erster_schritt.png\|thumb\|center~~\|Last-First Zuordnung~~]]		[[File:Erster_schritt.png\|thumb\|center]]
	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.		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.
	[[File:2._Schritt.png\|thumb\|center~~\|Last-First Zuordnung~~]]		[[File:2._Schritt.png\|thumb\|center]]
	Nach diesem Schema wird so lange weiter gearbeitet, bis das Sonderzeichen erreicht und die Originalsequenz rekonstruiert ist.<br><br>		Nach diesem Schema wird so lange weiter gearbeitet, bis das Sonderzeichen erreicht und die Originalsequenz rekonstruiert ist.<br><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>		=== Alignment === <br>
			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. <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 Zeilen übertragen.		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]]
	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 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]]
	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.
	~~[[File:Suche3.png\|thumb\|center\|Suche einer Sequenz~~]]

	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.		Der Suffix-Array an dieser Position ist '3'. Demzufolge beginnt die gesuchte Sequenz an der 3. Position in der Originalsequenz.
	[[File:Suche4.png\|thumb\|center~~\|Suche einer Sequenz~~]]		[[File:Suche4.png\|thumb\|center]]

	Diese Burrows-Wheeler Transformation kann mit jeder beliebigen Sequenz durchgeführt werden und ermöglicht eine effektive Suche nach einem lokalen Alignment.		Diese Burrows-Wheeler Transformation kann mit jeder beliebigen Sequenz durchgeführt werden und ermöglicht eine effektive Suche nach einem lokalen Alignment.

Mka: /* Burrows-Wheeler Transformation */

2021-01-31T10:47:53Z

Burrows-Wheeler Transformation

← Older revision		Revision as of 12:47, 31 January 2021
Line 2:		Line 2:
	<br>		<br>
	== Burrows-Wheeler Transformation ==		== Burrows-Wheeler Transformation ==
	Die Burrows-Wheeler ~~Induzierung~~ wurde in der Informatik ursprünglich zur Optimierung von Daten-Kompression entwickelt.<br>		Die Burrows-Wheeler Transformation wurde in der Informatik ursprünglich zur Optimierung von Daten-Kompression entwickelt.<br>
	Sie eignet sich auch gut zur effizienten Suche großer Texte und somit zur Suche eines optimalen Alignments.<br>		Sie eignet sich auch gut zur effizienten Suche großer Texte und somit zur Suche eines optimalen Alignments.<br>
			Ein BWT basierender Algorithmus wird zur Assemblierung der “reads” einer RNASeq verwendet.
	<br>		<br>

	'''Vorteile'''<br>		'''Vorteile'''<br>
	* Sehr schnell und verbraucht wenig Speicher<br>		* Sehr schnell und verbraucht wenig Speicher<br>