Warum ist dieses Wissen wichtig? Dynamische Programmierung ist eine der wichtigsten Techniken in der Bioinformatik. Ein sicheres Verständnis dieses Verfahrens ist Voraussetzung für die Analyse vieler der heute routinemäßig genutzten Heuristiken wie FASTA und BLAST. Daher ist es ganz wichtig, dass Sie diesen Algorithmus wirklich verstanden haben. Mit den unten folgenden Übungen können Sie dies testen. Erst beim Rechnen mit Papier und Bleistift zeigt sich, ob Sie das Verfahren drauf haben! 
Bezug Diese Übungen ergänzen das Kapitel 9 "Paarweiser Sequenzvergleich".  
 

Lernziel
Nach dem Bearbeiten der Übung sollten sie beherrschen:
  • Die Berechnung von Alignments mittels Dynamischer Programmierung.
  • Die Benutzung von Servern zur Berechnung von Alignments.
  • Die Interpretation der Ergebnisse.
 
     
Übung Ali_1, Interaktive Berechnung  
 
Benutzen Sie bitte das folgende Applet (programmiert von Dr. H. Liesegang, Göttingen) um ihr Verständnis zu überprüfen.
  Beachten Sie, dass hier mit Distanzen gerechnet wird.

Ändern Sie die Eingabesequenzen, sowie die Distanzwerte und studieren Sie die Effekte auf das Alignment.

  
     
Hinweis Voraussetzung für den Betrieb des Applets ist die Installation von Java auf Ihrem Rechner.
Interaktive Berechnung der Levenshtein-Distanz zwischen den Sequenzen A und B. 

In den Felder Gap, Match und Mismatch können die "Kosten" für das Einführen einer Lücke, den Match (Übereinstimmung zweier Symbole) und den Mismatch eingetragen werden.

Betätigen der Taste Clear löscht den Matrizeninhalt.

Betätigen der Taste Step stößt die Berechnung des nächsten Wertes an.

Betätigen der Taste Run bewirkt die Berechnung sämtlicher, noch ausstehender Werte. 

 
 
     

Alignments berechnet mit Scores
 
Für die folgenden Übungen gilt, sofern nichts anderes vereinbart:

s(C, C) = s(D, D) = +1 ,
s(C, D) = s(D, C) = -1 ,
s(gap, C) =  s(gap, C) =  s(D, gap) = s(gap,D) = s( gap ) = -2

Hierbei ist gap das Symbol für die Lücke

Wir arbeiten hier mit Scores!
 		  
     
 
Bestimmen Sie für die unten angegebenen Übungen jeweils mit Papier und Bleistift Scores für den Vergleich der Sequenzen und das Alignment. Übernehmen Sie Ihre Ergebnisse in das Protokoll.
 
 

 

  
Hinweise

Markieren Sie das Alignment (wenn mehrere möglich sind, das Ihrer Wahl) in der Matrix.

Drucken Sie hierfür dieses Dokument aus.

Es empfiehlt sich, in jeder Zelle Sij die drei Teilergebnisse einzutragen, ehe sie die maximalen Wert suchen. Beispielsweise ist es geschickt, die drei Werte wie folgt in einer Zelle einzutragen. Sie müssen sich hierfür jede Zelle in vier Teilzellen aufteilen. Zusätzlich sollten Sie die Pfade für das Backtracking markieren.

 

Si-1, j-1 + s(ai , bj) Si-1, j + s(ai , gap)
Si, j-1 + s(gap , bj) max-Wert

 

  
Übung Ali_2, Globales Alignment
     
  Benutzen Sie den Needleman-Wunsch Algorithmus, d. h. die Bedingung:
Sij = max { Si-1, j + s(ai , gap) , Si-1, j-1 + s(ai , bj) ,  Si, j-1 + s(gap , bj) }
     
 
    D C D D E G
  0 -2 -4 -6 -8 -10 -12
F -2            
C -4            
D -6            
E -8            
G -10            
 
     
 
Alignment: D C D D C C
           
 
     
     
Übung Ali_3, Lokales Alignment  
     
 
Benutzen Sie den Smith-Waterman Algorithmus, d. h. die Bedingung:
Sij = max { 0, Si-1, j + s(ai , gap ) ,  Si-1, j-1 + s(ai , bj) ,  S i , j-1 + s(gap , bj) }
 
Hinweise In die Felder sind bereits die Scores aus der BLOSUM62 Matrix eingetragen. Diese WErte entsprechen den Termen s(ai , bj), die nun individuell gewichtet sind.

 

  
 
    D V Y W A R D G
  0 0 0 0 0 0 0 0 0
A 0 -2 0 -2 -3 4 -1 -2 0
R 0 -2 -3 -2 -3 -1 5 -2 -2
Y 0 -2 -1 7 2 -2 -2 -3 -3
W 0 -4 -3 2 11 -3 -3 -4 -2
C 0 -3 -1 -2 -2 0 -3 -3 -3
Q 0 0 -2 -1 -2 -1 1 0 0
L 0 -4 1 -1 -2 -1 -2 -4 -4
I 0 -3 3 -1 -3 -1 -3 -3 -4
 
     
 
Alignment:                
               
     
Lösungen Hier finden Sie die Lösungen zu diesen Übungen.

  
Übung Ali_5, Hamming-Abstand  
     
  Ein Distanzmaß, dass in der Bioinformatik eine im Vergleich zum Levenshtein-Abstand untergeordnete Rolle spielt, jedoch in einigen Anwendungen verwendet wird, ist der Hamming-Abstand.  
 
Wie ist dieser Abstand definiert?
 
  Gegeben seien die beiden Sequenzen BESENKAMMER und REGENMACHER.  
 
Wie groß ist der Hamming-Abstand?
 
     
Übung Ali_6, Exon-Intron-Alignment  
     
  Betrachten Sie für die folgenden Übung folgendes Szenario:

Sie arbeiten in einem Laborexperiment mit dem Arylsulfatase-Gen von Chlamydomonas reinhardtii, dessen cDNA-Sequenz schon bekannt ist (accession number X52304). Für verschiedene Untersuchungen brauchen Sie auch dessen genomische Sequenz, die Sie über eine PCR-Strategie gewinnen wollen. Hier die Rohsequenz einer Ihrer PCR-Klone, die natürlich leicht fehlerbehaftet ist:
 

  
 
>Cars_genom
GGGGGAGAGCTGCTCCAACCCGTGGAAGGTGAGGCCTGGTCGGGCGTGTGTGCAGGGCTGCCGGC
GGTTGCGCGTGGGCAACAGTGGAAACTACAGTTGCATGCATGGGCACGANTTTATTCCCCTCCTC
TGTTTTTGCCTACAGATCCTGCACCCCGACAGCACCGTCAAGAACTTCACCCAGGCACTCAACTC
CAAGTACGACCGCATCTACAACGCAATCNGCCCCTTCACCTACAAGACGTGCCTGCAGTACCTGG
TGCGTTGCGCCGGGGGCTTGCCGCGTGTGTGGGGTGCGGGCACGCGGCCCAGGCCTGCTGTTGAC
CTTCTCACATGCAACGCTCACCCCNGNCCCGTACTAATTTCCATGCCTAACACACACCCACANGA
TTGGGACAACGAGGACAGTCAATTTAAGAC
 
 
Bestimmen Sie die Intron/Exon Struktur des Gens: Wie liegen diese Gensegmente zueinander?

 

  
Hinweise Erstellen Sie mit den EMBOSS-Programmen needle und water globale und lokale Alignments mit den Standardeinstellungen. Helfen Ihnen die Alignments weiter, um eine Exon-Intron-Struktur festzulegen?

Benutzen Sie bei der Eingaben für die affine Kostenfunktion unterschiedliche Werte, z.B. 20 für das Öffnen von Lücken.

Vergleichen Sie die Ausgabe mit der von Dotlet. Wie kommen Sie in beiden Fällen zur genauen Position der Introns?

Ändern Sie nun für das Programm water die Parameter, um ein zufrieden stellendes Alignment zu erhalten! Welche Werte müssen Sie ändern? Warum?
 		  
Übung Ali_7, Needleman-Wunsch/Smith-Waterman  
     
  Am EBI in Hinxton ist ein Server zugänglich, mit dem Sie die Algorithmen zum globalen und lokalen Sequenzalignment nutzen können.

Machen Sie sich mit der Oberfläche vertraut: Wie wählen Sie lokales und globales Alignment? 		 
 
Vergleichen Sie paarweise MS2_HUMAN, ADAM_CROAD, SLIT_DROME:
Wie unterscheiden sich die Sequenzen?
 
Erklären Sie bitte die unterschiedlichen Werte für globale und lokale Alignments.		  
Hinweise Lassen Sie für jedes Paar sowohl ein globales als auch ein lokales Alignment berechnen.

Wie groß ist jeweils der relative Anteil identischer und ähnlicher Residuen?
Wie hoch ist der Score?
Tragen Sie die Werte in eine Tabelle ein.
Bestimmen Sie die jeweils für die Kombination globales, lokales Alignment die Unterschiede hinsichtlich der Scores, der Anteile identischer Residuen und dem Anteil von Lücken. Wie erklären sich die Unterschiede?

Vergleichen Sie Ihre Ergebnisse mit den Befunden, die aus den Dotplot-Messungen stammen.
Werden andere als die vom Dotplot her bekannten Protein-Domänen als ähnlich identifiziert?

  
     

Was Sie jetzt verstanden haben sollten

 Die Berechnung von Alignments ist eine ganz wesentliche Aufgabe in der Bioinformatik. Deswegen ist ein genaues Verständnis der Verfahren enorm wichtig. Heuristiken, die optimale Algorithmen approximieren, werden verwendet, um die Geschwindigkeit von Datenbanksuchen zu erhöhen. Die dynamische Programmierung ist ein spezielles Verfahren zur Berechnung von optimalen Lösungen, das auch in anderen bioinformatischen Anwendungen eingesetzt werden kann.