3 Alignments - Revision history

Skl: /* Sequenzalignment */

2021-09-26T12:57:56Z

Sequenzalignment

← Older revision		Revision as of 14:57, 26 September 2021
Line 2:		Line 2:
	= Sequenzalignment =		= Sequenzalignment =
	Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können. <br>		Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können. <br>
	Es gibt enorm viele Möglichkeiten eine Sequenz an eine andere zu alignen. Deshalb benötigt man ~~speziell~~ Algorithmen, die die besten Möglichkeiten finden. Um zu bestimmen welches Alignment das beste ist, wird ein Bewertungsschema, der sogenannte ~~Score~~, angewandt. So kann die Übereinstimmung zweier Sequenzen miteinander quantitativ (mit Zahlen) verglichen werden. <br>		Es gibt enorm viele Möglichkeiten eine Sequenz an eine andere zu alignen. Deshalb benötigt man spezielle Algorithmen, die die besten Möglichkeiten finden. Um zu bestimmen welches Alignment das beste ist, wird ein Bewertungsschema, der sogenannte alignment score, angewandt. So kann die Übereinstimmung zweier Sequenzen miteinander quantitativ (mit Zahlen) verglichen werden. <br>
	Es werden nicht alle möglichen ~~Alignements~~ ausprobiert und dann deren Scores verglichen, um herauszufinden welches Alignment das beste ist. Mit dieser "brute force" Methode ergeben sich bei kurzen Sequenzen von 100 Basen schon 10<sup><big>75</big></sup> Alignmentmögichkeiten. Stattdessen werden Sequenzen mit Hilfe des "Dynamic Programming" ~~alignet~~. Es folgt dem Prinzip von "divide and conquer", also die Zerlegung des Problems in viele Unterprobleme, die nacheinander gelöst werden.		Es werden nicht alle möglichen Alignments ausprobiert und dann deren Scores verglichen, um herauszufinden welches Alignment das beste ist. Mit dieser "brute force" Methode ergeben sich bei kurzen Sequenzen von 100 Basen schon 10<sup><big>75</big></sup> Alignmentmögichkeiten. Stattdessen werden Sequenzen mit Hilfe des "Dynamic Programming" alignt. Es folgt dem Prinzip von "divide and conquer", also die Zerlegung des Problems in viele Unterprobleme, die nacheinander gelöst werden.
	Zudem ermöglicht das Sequenzalignment die Erkennung ähnlicher Domänen. Da oft sogar homologe Sequenzen, die von einer gemeinsamen Sequenz abstammen, durch indels, die im Laufe der ~~Zeit~~ aufgetreten sind, unterschiedliche Längen besitzen, ist es notwendig gaps Einzufügen um die Ähnlichkeit der beiden Sequenzen sichtbar zu machen (s. Smith-Waterman).		Zudem ermöglicht das Sequenzalignment die Erkennung ähnlicher Domänen. Da oft sogar homologe Sequenzen, die von einer gemeinsamen Sequenz abstammen, durch indels, die im Laufe der Evolution aufgetreten sind, unterschiedliche Längen besitzen, ist es notwendig gaps Einzufügen um die Ähnlichkeit der beiden Sequenzen sichtbar zu machen (s. Smith-Waterman).
	Anwenndungen finden Alignments im Sequenzvergeleich, z.B. bei phylogenetischen Untersuchungen.		Anwenndungen finden Alignments im Sequenzvergeleich, z.B. bei phylogenetischen Untersuchungen.

Skl: /* FASTA-Format */

2021-09-25T14:23:54Z

FASTA-Format

← Older revision		Revision as of 16:23, 25 September 2021
Line 78:		Line 78:
	# Zeile: Sequenz ID, Zeile startet mit ">"		# Zeile: Sequenz ID, Zeile startet mit ">"
	# Zeile: (optional) Kommentare		# Zeile: (optional) Kommentare
	~~--> weitere Zeilen~~: die Sequenz		# Zeile: die Sequenz
	* besteht aus zwei bis drei Zeilen pro Sequenz		* besteht aus zwei bis drei Zeilen pro Sequenz
	* entstammt der FASTA Software, wird heutzutage aber als universelles Format in der Bioinformatik genutzt		* entstammt der FASTA Software, wird heutzutage aber als universelles Format in der Bioinformatik genutzt

Skl: /* FASTA Format */

2021-09-25T14:23:20Z

FASTA Format

← Older revision		Revision as of 16:23, 25 September 2021
Line 72:		Line 72:
	[[File:Smith Waterman.jpg\|600px\|thumb\|center]]		[[File:Smith Waterman.jpg\|600px\|thumb\|center]]

	== FASTA Format ==		== FASTA-Format ==
	* FSTA ist ein Programm zur Suche von Sequenzen in Datenbanken also eine Alignment Software		* FSTA ist ein Programm zur Suche von Sequenzen in Datenbanken also eine Alignment Software
	* das FASTA-Format ist ein allgemienes Format zur Speicherung von Sequenzdaten (Protein und DNA) in Textformat		* das FASTA-Format ist ein allgemienes Format zur Speicherung von Sequenzdaten (Protein und DNA) in Textformat
	* das Format folg einem festen Aufbau:		* das Format folg einem festen Aufbau:
	# Zeile: Sequenz ID, Zeile startet mit ">"		# Zeile: Sequenz ID, Zeile startet mit ">"
			# Zeile: (optional) Kommentare
	--> weitere Zeilen: die Sequenz		--> weitere Zeilen: die Sequenz
			* besteht aus zwei bis drei Zeilen pro Sequenz
	* entstammt der FASTA Software, wird heutzutage aber als universelles Format in der Bioinformatik genutzt		* entstammt der FASTA Software, wird heutzutage aber als universelles Format in der Bioinformatik genutzt

Skl: /* FASTA Format */

2021-09-25T14:15:44Z

FASTA Format

← Older revision		Revision as of 16:15, 25 September 2021
Line 78:		Line 78:
	# Zeile: Sequenz ID, Zeile startet mit ">"		# Zeile: Sequenz ID, Zeile startet mit ">"
	--> weitere Zeilen: die Sequenz		--> weitere Zeilen: die Sequenz
	* entstammt der FASTA Software, wird heutzutage aber als universelles Format in der Bioinformatik genutzt		* entstammt der FASTA Software, wird heutzutage aber als universelles Format in der Bioinformatik genutzt
	*

Skl at 14:15, 25 September 2021

2021-09-25T14:15:33Z

← Older revision		Revision as of 16:15, 25 September 2021
Line 70:		Line 70:

	Score: Match: +3 \| Mismatch: 0 \| Gap: -1		Score: Match: +3 \| Mismatch: 0 \| Gap: -1
	[[File:Smith Waterman.jpg\|600px\|thumb\|~~left~~]]		[[File:Smith Waterman.jpg\|600px\|thumb\|center]]

			== FASTA Format ==
			* FSTA ist ein Programm zur Suche von Sequenzen in Datenbanken also eine Alignment Software
			* das FASTA-Format ist ein allgemienes Format zur Speicherung von Sequenzdaten (Protein und DNA) in Textformat
			* das Format folg einem festen Aufbau:
			# Zeile: Sequenz ID, Zeile startet mit ">"
			--> weitere Zeilen: die Sequenz
			* entstammt der FASTA Software, wird heutzutage aber als universelles Format in der Bioinformatik genutzt
			*

Skl: /* Smith-Waterman Algorithmus */

2021-09-23T09:13:38Z

Smith-Waterman Algorithmus

← Older revision		Revision as of 11:13, 23 September 2021
Line 58:		Line 58:
	</big>		</big>

	===Smith-Waterman Algorithmus===		==Smith-Waterman Algorithmus==
	Dynamic programming: "divide and conquer", Aufteilen des Problems in Subprobleme		Dynamic programming: "divide and conquer", Aufteilen des Problems in Subprobleme
	<br>		<br>

Skl at 09:09, 23 September 2021

2021-09-23T09:09:25Z

← Older revision		Revision as of 11:09, 23 September 2021
Line 2:		Line 2:
	= Sequenzalignment =		= Sequenzalignment =
	Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können. <br>		Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können. <br>
	Es gibt enorm viele Möglichkeiten eine Sequenz an eine andere zu ~~Assemblieren~~. Deshalb benötigt man speziell Algorithmen, die die besten Möglichkeiten finden. Um zu bestimmen welches Alignment das beste ist, wird ein Bewertungsschema, der sogenannte Score, angewandt. So kann die Übereinstimmung zweier Sequenzen miteinander quantitativ (mit Zahlen) verglichen werden. Zudem ermöglicht das Sequenzalignment die Erkennung ähnlicher Domänen ~~und erfordert das Einfügen~~ von gaps (s. Smith-Waterman).		Es gibt enorm viele Möglichkeiten eine Sequenz an eine andere zu alignen. Deshalb benötigt man speziell Algorithmen, die die besten Möglichkeiten finden. Um zu bestimmen welches Alignment das beste ist, wird ein Bewertungsschema, der sogenannte Score, angewandt. So kann die Übereinstimmung zweier Sequenzen miteinander quantitativ (mit Zahlen) verglichen werden. <br>
			Es werden nicht alle möglichen Alignements ausprobiert und dann deren Scores verglichen, um herauszufinden welches Alignment das beste ist. Mit dieser "brute force" Methode ergeben sich bei kurzen Sequenzen von 100 Basen schon 10<sup><big>75</big></sup> Alignmentmögichkeiten. Stattdessen werden Sequenzen mit Hilfe des "Dynamic Programming" alignet. Es folgt dem Prinzip von "divide and conquer", also die Zerlegung des Problems in viele Unterprobleme, die nacheinander gelöst werden.
			Zudem ermöglicht das Sequenzalignment die Erkennung ähnlicher Domänen. Da oft sogar homologe Sequenzen, die von einer gemeinsamen Sequenz abstammen, durch indels, die im Laufe der Zeit aufgetreten sind, unterschiedliche Längen besitzen, ist es notwendig gaps Einzufügen um die Ähnlichkeit der beiden Sequenzen sichtbar zu machen (s. Smith-Waterman).
			Anwenndungen finden Alignments im Sequenzvergeleich, z.B. bei phylogenetischen Untersuchungen.

	Man unterscheidet zwei verschiedenen Arten beim Sequenzalignment:		Man unterscheidet zwei verschiedenen Arten beim Sequenzalignment:

Skl: /* Alignments */

2021-09-21T16:41:35Z

Alignments

← Older revision		Revision as of 18:41, 21 September 2021
Line 1:		Line 1:

	= ~~Alignments~~ =		= Sequenzalignment =
	Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können.		Das optimale „Aneinander ausrichten“ von Sequenzen, sodass z.B. reads aus einer Sequenzierung an ein Referenzgenom ausgerichtet werden können. <br>
			Es gibt enorm viele Möglichkeiten eine Sequenz an eine andere zu Assemblieren. Deshalb benötigt man speziell Algorithmen, die die besten Möglichkeiten finden. Um zu bestimmen welches Alignment das beste ist, wird ein Bewertungsschema, der sogenannte Score, angewandt. So kann die Übereinstimmung zweier Sequenzen miteinander quantitativ (mit Zahlen) verglichen werden. Zudem ermöglicht das Sequenzalignment die Erkennung ähnlicher Domänen und erfordert das Einfügen von gaps (s. Smith-Waterman).

	~~→ Für ein Alignment werden spezielle Algorithmen benötigt.~~		Man unterscheidet zwei verschiedenen Arten beim Sequenzalignment:
	~~<br>~~
	~~<br>~~
	~~<u>Sequenz Alignments</u>~~
	* Ähnlichkeit quantitativ bestimmbar
	* Erkennung ähnlicher Domänen
	* erfordert das Einfügen von "gaps"

	== Globales Alignment ==		== Globales Alignment ==
	* ~~Ausrichtung auf~~ die ~~gleiche Länge~~		* Alignment zwischen zwei Sequenzen, die ähnlich lang sind und bei denen starke Sequenzhomologien erwartet werden
			* Vergleich von Gesamtsequenzen
	* alle Symbole werden berücksichtigt		* alle Symbole werden berücksichtigt
	* ~~Vergleich ähnlicher Sequenzen mit ähnlicher Länge~~		* zur Berechnung des optimalen Alignment Scores wird häufig der Needle-Wunsch Algorithmus benutzt


	<br>		<br>
	'''Beispiel''':<br>		'''Beispiel''':<br>
Line 45:		Line 43:
	* Alignment von Teilsequenzen		* Alignment von Teilsequenzen
	* Vergleich zweier sehr unterschiedlicher Sequenzen, die aber gleiche Motive besitzen		* Vergleich zweier sehr unterschiedlicher Sequenzen, die aber gleiche Motive besitzen
	*Suche einer Gensequenz im Genom		* z.B. die Suche einer Gensequenz im Genom
	<br>		<br>
	Beispiel:<br>		Beispiel:<br>

Mka: /* Smith-Waterman Algorithmus */

2021-01-31T10:34:55Z

Smith-Waterman Algorithmus

← Older revision		Revision as of 12:34, 31 January 2021
Line 64:		Line 64:
	M<sub>0,j</sub>=0<br>		M<sub>0,j</sub>=0<br>
	M<sub>k,0</sub>=0<br>		M<sub>k,0</sub>=0<br>
	[[File:Smith Waterman Algorithmus.jpg\|400px\|~~thumb~~]]		[[File:Smith Waterman Algorithmus.jpg\|400px\|frameless]]

	Das Alignment beginnt bei dem höchsten erzielten Score in der Matrix		Das Alignment beginnt bei dem höchsten erzielten Score in der Matrix

	Score: Match: +3 \| Mismatch: 0 \| Gap: -1		Score: Match: +3 \| Mismatch: 0 \| Gap: -1
	[[File:Smith Waterman.jpg\|600px\|thumb\|left]]		[[File:Smith Waterman.jpg\|600px\|thumb\|left]]

Mka: /* Lokales Alignment */

2021-01-31T10:30:30Z

Lokales Alignment

← Older revision		Revision as of 12:30, 31 January 2021
Line 56:		Line 56:
	\|}		\|}
	</big>		</big>
	~~<br>~~
	===Smith-Waterman Algorithmus===		===Smith-Waterman Algorithmus===
	Dynamic programming: "divide and conquer", Aufteilen des Problems in Subprobleme		Dynamic programming: "divide and conquer", Aufteilen des Problems in Subprobleme
Line 64:		Line 64:
	M<sub>0,j</sub>=0<br>		M<sub>0,j</sub>=0<br>
	M<sub>k,0</sub>=0<br>		M<sub>k,0</sub>=0<br>
	[[File:Smith Waterman Algorithmus.jpg\|~~500xp~~\|thumb\|~~center~~]]		[[File:Smith Waterman Algorithmus.jpg\|400px\|thumb]]
			Das Alignment beginnt bei dem höchsten erzielten Score in der Matrix

			Score: Match: +3 \| Mismatch: 0 \| Gap: -1
			[[File:Smith Waterman.jpg\|600px\|thumb\|left]]