Zweite Programmieraufgabe WS 05/06

Webversion. Dies ist die aktualisierte Version der Aufgabe. Bisherige Aktualisierungen gegenüber der Druckversion vom 30.11.2005: keine.

Code Review am Dienstag, den 10. Januar 2006

Erinnerung: die Bewertung der Programmieraufgabe geht in die Note ein. Diese Aufgabe bringt 12 Punkte, ist also die aufwändigste Programmieraufgabe. Verspätete Abgaben werden nicht berücksichtigt. Sie dürfen in Gruppen von maximal drei Personen zusammenarbeiten.

Drucken Sie Ihren Programmcode aus und geben Sie ihn mit ab.


Heuristisches Sequenzalignment


Implementieren Sie eine einfache Version des FASTA-Algorithmus.

Ihr Algorithmus soll zwei Sequenzen im FASTA-Format und eine Scoring-Matrix einlesen können und ein möglichst gutes Alignment der beiden Sequenzen in möglichst kurzer Zeit ausgeben.

Beispiele für Eingabedateien finden Sie weiter unten.

Realisieren Sie die folgenden Schritte:

  1. Finden Sie hot spots mittels Hashing.
  2. Verketten Sie hot spots zu diagonal runs. Testen Sie hier eine geeignete Strategie zur Verkettung. Welche nehmen Sie und warum?
  3. Bewerten Sie die diagonal runs mit Hilfe der eingelesenen Scoring-Matrix.
  4. Bauen Sie den chaining graph aus den diagonal runs auf. Wählen Sie geeignete Kosten für die Kanten. Welche haben Sie genommen und warum?
  5. Berechnen Sie den schwersten Teilpfad in dem Graphen.
  6. Geben Sie auf der Basis der bisherigen Schritte ein möglichst gutes lokales Alignment, dessen Score und die Laufzeit (wenn möglich CPU-Time) aus. Welche Strategie haben Sie gewählt, um das Alignment zu berechnen und warum?


Sequenzen und Scoring-Matrizen

Hier ist schon mal eine Scoring-Matrix und eine Sequenz zum Testen:

blosum62.mat
P43652.fasta
anotherseq.fasta
abitlongerseq.fasta
onemoreseq.fasta



Gunnar Klau 2005-11-30