Fünfte Aufgabe (Globales Alignment)

Übungen zu
Algorithmische Bioinformatik
Aufgabe 5
Philippe Thomas
Samira Jaeger: Introduction to Bioinformatics, Exercises
1
Wettbewerb Aufgabe 4
Philippe Thomas: Übungen Algorithmische Bioinformatik
2
Wettbewerb
Grp1
Grp2
Grp3
Grp4
Grp5
Challenge 1
3
1
0
2
0
Challenge 2
3
2
0
2
0
Challenge3a
0
0
3
2
1
Challenge3b
0
0
2
3
1
Challenge 4
2
0
1
3
0
Philippe Thomas: Übungen Algorithmische Bioinformatik
3
Daten
●
●
Wir verwenden neue Daten
Im Web finden Sie
●
●
Fünf FASTA Dateien, die jeweils 11 Sequenzen enthalten
Jede Datei enthält Sequenzen einer Spezies
●
●
Die i-ten Sequenzen der Dateien sind Sequenzen desselben
Genes in den verschiedenen Spezies
●
●
Fruchtfliege, Mensch, Fadenwurm, Maus, Schimpanse
D.h. homologe Sequenzen
Eine Datei, die eine Substitutionsmatrix für DNA in einfach lesbarer
Form enthält (Dna.txt)
●
Inklusive Werte für Insertion / Deletion
Philippe Thomas: Übungen Algorithmische Bioinformatik
4
1.) Globales Alignment (10P)
●
Schreiben Sie ein Programm, dass
●
●
●
Alle 6 Daten einliest
Die Sequenzen aller homologen Gene miteinander vergleicht und
pro Gen alle paarweisen globalen Ähnlichkeiten ausgibt
Für die erste Sequenz (hier tRNA) alle optimalen Alignments
ausgibt
Sequenz 1
Mensch
Mensch
Maus
Maus
Schimpanse
Fadenwurm
Fliege
?
?
?
?
?
?
?
?
?
Schimpanse
Fadenwurm
Sequenz 2
…
Philippe Thomas: Übungen Algorithmische Bioinformatik
?
5
Ausgabeformat (paarweise Ähnlichkeiten)
…
Philippe Thomas: Übungen Algorithmische Bioinformatik
6
Ausgabeformat (optimale Alignments)
[tRNA] dro vs. cae: score is -54
Number of optimal Alignments = 1
1.)
ATGACAAA
.|-|||||
GT-ACAAA
[tRNA] mus vs. hom: score is 16
Number of optimal Alignments = XY
1.)
ATGACAAA
.|-|||||
GT-ACAAA
2.) …
Philippe Thomas: Übungen Algorithmische Bioinformatik
7
2.) Anzahl optimaler Alignemts (6P)
●
●
In der Regel kann der optimale globale Alignmentscore
von mehreren Alignments erreicht werden
Wir suchen die Zahl optimaler Alignments
●
●
●
Eine Möglichkeit, diese zu finden, ist es, in O(n*m) den optimalen Score
zu bestimmten und dann alle Pfade per Traceback abzulaufen und zu
zählen
Da es theoretisch exponentiell viele Pfade geben kann (siehe auch
nächste Aufgabe), kann das sehr teuer sein
Aufgabe: Entwickeln Sie einen Algorithmus, der in
O(n*m) die Zahl optimaler Alignments zwischen zwei
Zeichenketten A mit |A|=n und B mit |B|=m berechnet
●
●
Die aktuellen Alignments sind nicht gefragt
Hinweis: Dynamische Programmierung hilft!
Philippe Thomas: Übungen Algorithmische Bioinformatik
8
3.) Anzahl möglicher Pfade (4P)
●
Geben Sie eine Formel an, die die Zahl aller Pfade durch
eine Matrix der Größe m*n bestimmt
●
Rekursionsformel reicht
Philippe Thomas: Übungen Algorithmische Bioinformatik
9
Wettbewerb
●
Berechnen Sie das globale Alignment möglichst schnell
●
Tipp: K-Band könnte helfen
●
●
Aber: Bei sehr unähnlichen Sequenzen braucht man mit iterativem
k-Band länger
Außerdem: Sequenzen sind nicht exakt gleich lang
Philippe Thomas: Übungen Algorithmische Bioinformatik
10
Programmaufruf
●
Indexierung muss wie folgt aufrufbar sein:
●
●
●
java jar assignment5grx.jar f1 f2 f3 f4 f5 subfile
●
f1f5 … 5Speziesdateien
●
subfile … Substitutionsmatrix
●
Ausgabe auf stdout
Für die erste Gengruppe alle optimalen Alignments
Pro Gen Ausgabe aller paarweisen Scores
Philippe Thomas: Übungen Algorithmische Bioinformatik
11
Abgabe
●
●
Bis Montag den 13.1 um 23:59
Bitte die geschätzte Bearbeitungszeit mitteilen
●
●
Als eigene Datei time.txt
●
Z.B.: 15 Stunden pro Person (3 Personen)
Abgabe per Goya:
●
●
Lauffähige JAR Datei (assignment5-grXY.jar)
●
Quelltext (im JAR)
●
Abgaben ohne Quelltext werden ignoriert
●
JAR vor Abgabe testen
PDF mit Lösung zu Aufgabe 1 und 2
Philippe Thomas: Übungen Algorithmische Bioinformatik
12

Download Report