4.Burrows-Wheeler - Revision history

Mka: /* Aufgabe 1 */

2021-01-31T17:29:43Z

Aufgabe 1

← Older revision		Revision as of 19:29, 31 January 2021
Line 5:		Line 5:
	'''a''': Wofür wird der Burrows-Wheeler Algorithmus verwendet? Welche Funktion besitzt		'''a''': Wofür wird der Burrows-Wheeler Algorithmus verwendet? Welche Funktion besitzt
	er?		er?
			*Ursprünglich zur Datenkompression entwickelt: In der Transformation ergeben sich längere Abschnitte sich wiederholender Symbole, was Kompression ermöglicht
	~~Der BWA wird in der Informatik~~ zur ~~Datenkomprimierung verwendet.~~ In der Transformation ergeben sich längere Abschnitte sich wiederholender Symbole, ~~die~~ Kompression ~~ermöglichen~~.		*Teilstringsuche kann in der Transformation durchgeführt werden.
	In der Bioinformatik ~~wird er dazu verwendet um Sequenzabschnitte in großen Sequenzen~~		*In der Bioinformatik -> read mapping nach sequenzing
	~~zu finden. Eine Anwendung wäre zum Beispiel die Position von reads an einem~~		*Sortieren ist ohne Informationsverlust möglich: Rücktransformation möglich
	~~Referenzgenom zu bestimmen. Besonders an der Transformation~~ ist~~, dass eine~~ Rücktransformation ~~problemlos~~ möglich ~~ist und dass es keinen Informationsverlust bei dem Prozess gibt.~~


Line 18:		Line 17:


	Schritte:		'''Schritte:'''

	~~'''~~1. Generiere alle zyklischen Verschiebungen der Template Sequenz T~~'''~~		1. Generiere alle zyklischen Verschiebungen der Template Sequenz T

	~~'''~~2. Sortiere die Verschiebungen alphabetisch~~'''~~		2. Sortiere die Verschiebungen alphabetisch

	~~'''~~3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix~~'''~~		3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix


Line 72:		Line 71:
	finden wollen?		finden wollen?

	Für diese Anwendung benötigt man die Zahlenwerte, die man den Verschiebungen am Anfang gegeben hat. Man schaut in der 1. Spalte nach dem Intervall mit dem letzten Buchstaben der gesuchten Sequenz, geht damit dann zum entsprechenden Intervall rechts in der letzten Zeile und verkleinert es an den Enden die nicht der Sequenz entsprechen~~. Die Zeile an der man am Ende in der linken Zeile endet ist die Position an der die Sequenz beginnt, wenn man +1 hinzufügt~~.		Für diese Anwendung benötigt man die Zahlenwerte, die man den Verschiebungen am Anfang gegeben hat. Man schaut in der 1. Spalte nach dem Intervall mit dem letzten Buchstaben der gesuchten Sequenz, geht damit dann zum entsprechenden Intervall rechts in der letzten Zeile und verkleinert es an den Enden die nicht der Sequenz entsprechen.

	[[File:U4A1d1.PNG\|thumb~~\|Anfang des Suchalgorithmus~~]]		[[File:U4A1d1.PNG\|thumb]]

	Im ersten Schritt sehen wir, dass wir ein Zweierintervall haben für C, wenn wir das nach Rechts verfolgen, sehen wir dass die untere Position nicht die gewünschte zweite Position besitzt. Deshalb wird das Intervall unter verkleinert.		Im ersten Schritt sehen wir, dass wir ein Zweierintervall haben für C, wenn wir das nach Rechts verfolgen, sehen wir dass die untere Position nicht die gewünschte zweite Position besitzt. Deshalb wird das Intervall unter verkleinert.

	[[File:~~U4A1d2~~.~~PNG~~\|thumb~~\|Fortführung des Suchalgorithmus~~]]		[[File:Alignment4.png\|thumb]]
			Der Rest ist aufgrund der Tatsache, dass die Intervallsgröße nur noch 1 ist, relativ einfach. Dabei wird lediglich die Sequenz weiter rückwärts durchlaufen bis man auf den ersten Buchstaben der gesuchten Sequenz trifft. Die zugehörige Nummer entspricht dem Startpunkt der gesuchten Sequenz. Die Sequenz fängt in String Nummer 4 an.
	Der Rest ist aufgrund der Tatsache, dass die Intervallsgröße nur noch 1 ist, relativ einfach. Dabei wird lediglich die Sequenz weiter rückwärts durchlaufen bis man ~~in der sortierten Spalte~~ auf den ~~erste~~ Buchstaben der gesuchten Sequenz trifft. Die zugehörige Nummer ~~(+1, da bei Null angefangen wurde zu nummerieren)~~ entspricht dem Startpunkt der gesuchten Sequenz. Die Sequenz fängt in String Nummer 3 an~~, also begint die Sequenz an Position 3+1= 4~~.		[[File:Alignment5.png\|thumb]]

Pge at 20:21, 3 October 2020

2020-10-03T20:21:27Z

← Older revision		Revision as of 22:21, 3 October 2020
Line 54:		Line 54:
	BWT(T)= G$CCGTTAAG		BWT(T)= G$CCGTTAAG

	c) Führen Sie nun eine Rücktransformation der transformierten Sequenz (aus Teil b)		'''c''': Führen Sie nun eine Rücktransformation der transformierten Sequenz (aus Teil b)
	mithilfe der „last first“ Zuordnung durch. Beschreiben Sie ihr Vorgehen anhand der		mithilfe der „last first“ Zuordnung durch. Beschreiben Sie ihr Vorgehen anhand der
	einzelnen Teilschritte.		einzelnen Teilschritte.
Line 69:		Line 69:
	Sequenz: AGTGCCATG$		Sequenz: AGTGCCATG$

	d) Wie gehen Sie vor, wenn Sie die Teilsequenz GCC in der gegebenen Sequenz		'''d''': Wie gehen Sie vor, wenn Sie die Teilsequenz GCC in der gegebenen Sequenz
	finden wollen?		finden wollen?

Line 80:		Line 80:
	[[File:U4A1d2.PNG\|thumb\|Fortführung des Suchalgorithmus]]		[[File:U4A1d2.PNG\|thumb\|Fortführung des Suchalgorithmus]]

	Der Rest ist aufgrund der Tatsache, dass die Intervallsgröße nur noch 1 ist, relativ einfach. Dabei wird lediglich die Sequenz weiter rückwärts durchlaufen bis man in der sortierten Spalte auf den erste Buchstaben ~~de gsuchten~~ Sequenz trifft. Die zugehörige Nummer (+1 da bei Null angefangen wurde zu nummerieren) entspricht dem Startpunkt der gesuchten Sequenz. Die Sequenz fängt in String Nummer 3 an, also begint die Sequenz an Position 3+1= 4.		Der Rest ist aufgrund der Tatsache, dass die Intervallsgröße nur noch 1 ist, relativ einfach. Dabei wird lediglich die Sequenz weiter rückwärts durchlaufen bis man in der sortierten Spalte auf den erste Buchstaben der gesuchten Sequenz trifft. Die zugehörige Nummer (+1, da bei Null angefangen wurde zu nummerieren) entspricht dem Startpunkt der gesuchten Sequenz. Die Sequenz fängt in String Nummer 3 an, also begint die Sequenz an Position 3+1= 4.

Pge: /* Aufgabe 1 */

2020-10-03T20:14:17Z

Aufgabe 1

← Older revision		Revision as of 22:14, 3 October 2020
Line 20:		Line 20:
	Schritte:		Schritte:

	'''1. Generiere alle zyklischen Verschiebungen der Template Sequenz T		'''1. Generiere alle zyklischen Verschiebungen der Template Sequenz T'''

	2. Sortiere die Verschiebungen alphabetisch		'''2. Sortiere die Verschiebungen alphabetisch'''

	3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix'''		'''3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix'''

Pge: /* Aufgabe 1 */

2020-10-03T20:13:42Z

Aufgabe 1

← Older revision		Revision as of 22:13, 3 October 2020
Line 20:		Line 20:
	Schritte:		Schritte:

	1. Generiere alle zyklischen Verschiebungen der Template Sequenz T		'''1. Generiere alle zyklischen Verschiebungen der Template Sequenz T

	2. Sortiere die Verschiebungen alphabetisch		2. Sortiere die Verschiebungen alphabetisch

	3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix		3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix'''

Pge: /* Aufgabe 1 */

2020-10-03T20:13:17Z

Aufgabe 1

← Older revision		Revision as of 22:13, 3 October 2020
Line 3:		Line 3:
	== Aufgabe 1 ==		== Aufgabe 1 ==

	a) Wofür wird der Burrows-Wheeler Algorithmus verwendet? Welche Funktion besitzt		'''a''': Wofür wird der Burrows-Wheeler Algorithmus verwendet? Welche Funktion besitzt
	er?		er?

	Der BWA wird in der Informatik zur Datenkomprimierung verwendet. In der		Der BWA wird in der Informatik zur Datenkomprimierung verwendet. In der Transformation ergeben sich längere Abschnitte sich wiederholender Symbole, die Kompression ermöglichen.
	Bioinformatik wird er dazu verwendet um Sequenzabschnitte in großen Sequenzen		In der Bioinformatik wird er dazu verwendet um Sequenzabschnitte in großen Sequenzen
	zu finden. Eine Anwendung wäre zum Beispiel die Position von reads an einem		zu finden. Eine Anwendung wäre zum Beispiel die Position von reads an einem
	Referenzgenom zu bestimmen. Besonders an der Transformation ist, dass eine Rücktransformation problemlos möglich ist und dass es keinen Informationsverlust bei dem Prozess gibt.		Referenzgenom zu bestimmen. Besonders an der Transformation ist, dass eine Rücktransformation problemlos möglich ist und dass es keinen Informationsverlust bei dem Prozess gibt.

	b) Nennen Sie die Schritte, welche für eine Burrows-Wheeler Transformation
			'''b''': Nennen Sie die Schritte, welche für eine Burrows-Wheeler Transformation
	durchgeführt werden müssen und zeigen Sie dies an folgender Sequenz:		durchgeführt werden müssen und zeigen Sie dies an folgender Sequenz:
	AGTGCCATG$.		AGTGCCATG$.

Pge: /* Aufgabe 1 */

2020-05-15T12:04:58Z

Aufgabe 1

← Older revision		Revision as of 14:04, 15 May 2020
Line 18:		Line 18:

	Schritte:		Schritte:

	1. Generiere alle zyklischen Verschiebungen der Template Sequenz T		1. Generiere alle zyklischen Verschiebungen der Template Sequenz T

	2. Sortiere die Verschiebungen alphabetisch		2. Sortiere die Verschiebungen alphabetisch

	3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix		3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix


	Zuerst werden alle cyclischen Verschiebungen der Sequenz aufgeschrieben und		Zuerst werden alle cyclischen Verschiebungen der Sequenz aufgeschrieben und

Pge at 12:04, 15 May 2020

2020-05-15T12:04:12Z

← Older revision		Revision as of 14:04, 15 May 2020
Line 15:		Line 15:
	AGTGCCATG$.		AGTGCCATG$.
	Wie lautet der Index dieser Transformation?		Wie lautet der Index dieser Transformation?


			Schritte:
			1. Generiere alle zyklischen Verschiebungen der Template Sequenz T
			2. Sortiere die Verschiebungen alphabetisch
			3. Die Burrows-Wheeler Transformation BWT (T) ist die letzte Spalte der sortierten Matrix

	Zuerst werden alle cyclischen Verschiebungen der Sequenz aufgeschrieben und		Zuerst werden alle cyclischen Verschiebungen der Sequenz aufgeschrieben und

Pge at 11:59, 15 May 2020

2020-05-15T11:59:39Z

← Older revision		Revision as of 13:59, 15 May 2020
Line 10:		Line 10:
	zu finden. Eine Anwendung wäre zum Beispiel die Position von reads an einem		zu finden. Eine Anwendung wäre zum Beispiel die Position von reads an einem
	Referenzgenom zu bestimmen. Besonders an der Transformation ist, dass eine Rücktransformation problemlos möglich ist und dass es keinen Informationsverlust bei dem Prozess gibt.		Referenzgenom zu bestimmen. Besonders an der Transformation ist, dass eine Rücktransformation problemlos möglich ist und dass es keinen Informationsverlust bei dem Prozess gibt.

	b) Nennen Sie die Schritte, welche für eine Burrows-Wheeler Transformation		b) Nennen Sie die Schritte, welche für eine Burrows-Wheeler Transformation
	durchgeführt werden müssen und zeigen Sie dies an folgender Sequenz:		durchgeführt werden müssen und zeigen Sie dies an folgender Sequenz:

Pge: Pge moved page Übung 4 to 4.Burrows-Wheeler

2020-05-15T10:36:50Z

Pge moved page Übung 4 to 4.Burrows-Wheeler

← Older revision

Revision as of 12:36, 15 May 2020

Pge at 10:36, 15 May 2020

2020-05-15T10:36:36Z

← Older revision		Revision as of 12:36, 15 May 2020
Line 1:		Line 1:
	~~Diese Übung war am 08.05.2019 abzugeben.~~

	== Aufgabe 1 ==		== Aufgabe 1 ==