Bio

03 Der Needleman-Wunsch-Algorithmus

Einführung in die Bioinformatik Vorbereiten der Software Grundlagen der objektorientierten Programmierung Einfaches Codebeispiel – manipulieren eines strings Referenzieren einzelner Zeichen in einem string Generieren einer zufälligen Aminosäure-Sequenz Scoring von Alignments Prüfen auf Identität Bewerten von Mutationen – Substitution Matrix Bewerten eines Alignments Der Needleman-Wunsch-Algorithmus Die F-Matrix (abstrakt) Auswählen des Alignments (abstrakt) F-Matrix (Code) Auswählen des Alignments (Code) Die F-Matrix (abstrakt) Der Needleman-Wunsch-Algorithmus geht bei der Berechnung des idealen Alignements in zwei Schritten vor, um exponentiell skalierende Rechenzeit zu vermeiden. Zunächst wird die sogenannte F-Matrix berechnet, aus welcher anschließend das ideale Alignment zusammengesetzt wird. Zur Veranschaulichung alignen wir die Sequenzen GACFC und GCFHC. Jedes Feld in der Matrix (jede Zelle der Tabelle) beinhaltet einen Score. Diese Punktzahl ist jene, die auf dem Weg zur Berechnung des Feldes gesammelt wurde. Zur Berechnung einer Zelle sind immer die Felder links oben, oben und links notwendig: Unter den drei Feldern wird jenes gewählt, durch…