Warum ist dieses Wissen wichtig? Dynamische Programmierung ist eine wichtiges Verfahren der Bioinformatik. Ein sicheres Verständnis dieser Methode ist Voraussetzung für die Analyse der routinemäßig genutzten Heuristiken wie FASTA und BLAST und das Verständnis von Algorithmen, mit denen z. B. Hidden-Markov-Modelle ausgewertet werden. 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 Ihr Wissen! 
Bezug Diese Übungen ergänzen das Kapitel 9 "Paarweiser Sequenzvergleich".
 

Lernziel

 Nach dem Bearbeiten der Übung sollten sie beherrschen:
  • Das Berechnen von Alignments mittels dynamischer Programmierung.
  • Das Benutzen von Servern zur Berechnung von Alignments.
  • Das Interpretieren der Ergebnisse.
   
Übung Dotplot_1
Dotplots sind sehr einfache und wenig empfindliche Verfahren, um gemeinsame Teilsequenzen zu bestimmen. Sie benutzen jedoch dieselbe Datenstruktur wie aufwändigere Alignmentverfahren. Rekapitulieren Sie bitte, wie aus der gefüllten Matrix M das Infix abgeleitet wird. Gegeben seien die folgenden Sequenzen:
   
SEQ_A   G H R Q S G G
SEQ_B   S G G R G    

 
  Berechnen Sie mit Papier und Bleistift einen Dotplot.
Es gelte folgende Bedingung für das Füllen der Matrix M:
 
Bedingung für Dotplot
  Diskutieren Sie das Ergebnis; wo liegt des längste gemeinsame Infix?
   
Lösung Hier finden Sie die Lösung zur Aufgabe.
   

Berechnen von Alignments mithilfe von Scores
  Nun wollen wir dynamische Programmierung nutzen, um zwei Sequenzen zu Alignieren. Für die folgenden Übungen gelten folgende Scorewerte:

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.

   
 
Bestimmen Sie für die unten angegebenen Übungen jeweils mit Papier und Bleistift Scores für den Vergleich der Sequenzen und die resultierenden Alignments. Markieren Sie das Alignment (wenn mehrere möglich sind, das Ihrer Wahl) in der Matrix.
 

Drucken Sie hierfür dieses Dokument aus.
Hinweise Es empfiehlt sich, in jeder Zelle Sij die drei Teilergebnisse einzutragen, ehe Sie die maximalen Werte 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_1, 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_2, 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, um die Berechnung zu erleichtern, 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_3, Exon-Intron-Alignment
   
Mit der folgenden übung soll klar gemacht werden, dass Standardeinstellungen (Defaults) nicht für alle Fragestellungen die optimalen Ergebnisse liefern. Betrachten Sie für die folgenden Übung folgendes Szenario:

In einem Laborexperiment wird das Arylsulfatase-Gen von Chlamydomonas reinhardtii untersucht, dessen cDNA-Sequenz schon bekannt ist (accession number X52304). Für verschiedene Untersuchungen wird jedoch auch dessen genomische Sequenz benötigt, die über eine PCR-Strategie gewonnen werden soll.

Die genomische Sequenzen enthält bei diesem Organismus Introns, während eine cDNA-Sequenz nur aus Exons besteht. Hier folgt die Rohsequenz eines PCR-Klons, die aufgrund der Technologie 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 jeweils paarweise globale und lokale Alignments mit den Standardeinstellungen. Alignieren Sie die Sequenz von Cars_genom mit der DNA-Sequenz, die zu X52304 gehört. Helfen Ihnen die Alignments weiter, um eine Exon-Intron-Struktur festzulegen?

Nutzen Sie das Software-Angebot des EBI in Hinxton.

Ändern Sie nun für das Programm water die Parameter, um ein zufriedenstellendes Alignment zu erhalten. Welche Werte müssen Sie ändern? Warum? Überlegen Sie sich, dass Sie DNA-Sequenzen betrachten und welchen Einfluss die beiden Parameter der affinen Kostenfunktion auf die Länge und Anzahl von Lücken haben. Testen Sie unterschiedliche Werte, z.B. 20 für das Öffnen von Lücken.

Machen Sie sich bitte klar, in welche der beiden Sequenzen das Alignment KEINE Lücken einführen darf!
   
Übung Ali_7, Needleman-Wunsch/Smith-Waterman
  Diese Übung soll plausibel machen, dass die sich einstellenden Ähnlichkeitswerte beim Vergleich identischer Sequenzen vom benutzten Alignmentverfahren abhängen.

Nutzen Sie wiederum die Server des EBI, um globale und lokale Sequenzalignment für bereits vertraute Sequenzen zu berechnen.

 
MS2_HUMAN (P78325)
MRGLGLWLLGAMMLPAIAPSRPWALMEQYEVVLPRRLPGPRVRRALPSHLGLHPERVSYVLGATGHNFTLHLRKNRDLLG
SGYTETYTAANGSEVTEQPRGQDHCLYQGHVEGYPDSAASLSTCAGLRGFFQVGSDLHLIEPLDEGGEGGRHAVYQAEHL
LQTAGTCGVSDDSLGSLLGPRTAAVFRPRPGDSLPSRETRYVELYVVVDNAEFQMLGSEAAVRHRVLEVVNHVDKLYQKL
NFRVVLVGLEIWNSQDRFHVSPDPSVTLENLLTWQARQRTRRHLHDNVQLITGVDFTGTTVGFARVSAMCSHSSGAVNQD
HSKNPVGVACTMAHEMGHNLGMDHDENVQGCRCQERFEAGRCIMAGSIGSSFPRMFSDCSQAYLESFLERPQSVCLANAP
DLSHLVGGPVCGNLFVERGEQCDCGPPEDCRNRCCNSTTCQLAEGAQCAHGTCCQECKVKPAGELCRPKKDMCDLEEFCD
GRHPECPEDAFQENGTPCSGGYCYNGACPTLAQQCQAFWGPGGQAAEESCFSYDILPGCKASRYRADMCGVLQCKGGQQP
LGRAICIVDVCHALTTEDGTAYEPVPEGTRCGPEKVCWKGRCQDLHVYRSSNCSAQCHNHGVCNHKQECHCHAGWAPPHC
AKLLTEVHAASGSLPVLVVVVLVLLAVVLVTLAGIIVYRKARSRILSRNVAPKTTMGRSNPLFHQAASRVPAKGGAPAPS
RGPQELVPTTHPGQPARHPASSVALKRPPPAPPVTVSSPPFPVPVYTRQAPKQVIKPTFAPPVPPVKPGAGAANPGPAEG
AVGPKVALKPPIQRKQGAGAPTAP
ADAM_CROAD (P34179)
QQNLPQRYIELVVVADRRVFMKYNSDLNIIRTRVHEIVNIINGFYRSLNIDVSLVNLEIWSGQDPLTIQSSSSNTLNSEG
LWREKVLLNKKKKDNAQLLTAIEFKCETLGKAYLNSMCNPRSSVGIVKDHSPINLLVAVTMAHELGHNLGMEHDGKDCLR
GASLCIMRPGLTPGRSYEFSDDSMGYYQKFLNQYKPQCILNKP
SLIT_DROME (P24014)
MAAPSRTTLMPPPFRLQLRLLILPILLLLRHDAVHAEPYSGGFGSSAVSSGGLGSVGIHIPGGGVGVITEARCPRVCSCT
GLNVDCSHRGLTSVPRKISADVERLELQGNNLTVIYETDFQRLTKLRMLQLTDNQIHTIERNSFQDLVSLERLDISNNVI
TTVGRRVFKGAQSLRSLQLDNNQITCLDEHAFKGLVELEILTLNNNNLTSLPHNIFGGLGRLRALRLSDNPFACDCHLSW
LSRFLRSATRLAPYTRCQSPSQLKGQNVADLHDQEFKCSGLTEHAPMECGAENSCPHPCRCADGIVDCREKSLTSVPVTL
PDDTTDVRLEQNFITELPPKSFSSFRRLRRIDLSNNNISRIAHDALSGLKQLTTLVLYGNKIKDLPSGVFKGLGSLRLLL
LNANEISCIRKDAFRDLHSLSLLSLYDNNIQSLANGTFDAMKSMKTVHLAKNPFICDCNLRWLADYLHKNPIETSGARCE
SPKRMHRRRIESLREEKFKCSWGELRMKLSGECRMDSDCPAMCHCEGTTVDCTGRRLKEIPRDIPLHTTELLLNDNELGR
ISSDGLFGRLPHLVKLELKRNQLTGIEPNAFEGASHIQELQLGENKIKEISNKMFLGLHQLKTLNLYDNQISCVMPGSFE
HLNSLTSLNLASNPFNCNCHLAWFAECVRKKSLNGGAARCGAPSKVRDVQIKDLPHSEFKCSSENSEGCLGDGYCPPSCT
CTGTVVACSRNQLKEIPRGIPAETSELYLESNEIEQIHYERIRHLRSLTRLDLSNNQITILSNYTFANLTKLSTLIISYN
KLQCLQRHALSGLNNLRVVSLHGNRISMLPEGSFEDLKSLTHIALGSNPLYCDCGLKWFSDWIKLDYVEPGIARCAEPEQ
MKDKLILSTPSSSFVCRGRVRNDILAKCNACFEQPCQNQAQCVALPQREYQCLCQPGYHGKHCEFMIDACYGNPCRNNAT
CTVLEEGRFSCQCAPGYTGARCETNIDDCLGEIKCQNNATCIDGVESYKCECQPGFSGEFCDTKIQFCSPEFNPCANGAK
CMDHFTHYSCDCQAGFHGTNCTDNIDDCQNHMCQNGGTCVDGINDYQCRCPDDYTGKYCEGHNMISMMYPQTSPCQNHEC
KHGVCFQPNAQGSDYLCRCHPGYTGKWCEYLTSISFVHNNSFVELEPLRTRPEANVTIVFSSAEQNGILMYDGQDAHLAV
ELFNGRIRVSYDVGNHPVSTMYSFEMVADGKYHAVELLAIKKNFTLRVDRGLARSIINEGSNDYLKLTTPMFLGGLPVDP
AQQAYKNWQIRNLTSFKGCMKEVWINHKLVDFGNAQRQQKITPGCALLEGEQQEEEDDEQDFMDETPHIKEEPVDPCLEN
KCRRGSRCVPNSNARDGYQCKCKHGQRGRYCDQGEGSTEPPTVTAASTCRKEQVREYYTENDCRSRQPLKYAKCVGGCGN
QCCAAKIVRRRKVRMVCSNNRKYIKNLDIVRKCGCTKKCY
   
  Vergleichen Sie paarweise MS2_HUMAN, ADAM_CROAD, SLIT_DROME. Wie unterscheiden sich die Sequenzen?
 
 
Hinweise Lassen Sie für jedes Paar sowohl ein globales als auch ein lokales Alignment berechnen.

Erklären Sie bitte die unterschiedlichen Ergebnisse für globale und lokale Alignments:

Wie groß ist jeweils der relative Anteil identischer und ähnlicher Residuen?
Wie hoch ist der Score?
Tragen Sie die Werte in eine Tabelle ein.
Vergleichen Sie für Sequenzpaare die Ergebnisse, die Sie für das globale und lokale Alignment errechnen. Studieren Sie die Unterschiede hinsichtlich der Scores, der Anteile identischer Residuen und dem Anteil von Lücken. Warum ergeben sich Unterschiede?

   

Was Sie jetzt verstanden haben sollten

 Das Berechnen 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.