Programmierpraktikum Algorithmen in der Bioinformatik - WS08

Betreuer

Martin Mann

Ziel

Ziel ist das selbstständige Erarbeiten und Implementieren einer überschaubaren Anzahl von Algorithmen aus einem Teilgebiet der Bioinformatik. Hierbei soll auf Basis einer Literaturrecherche für jeden Algorithmus eine umfassende Beschreibung in Html und eine Implementierung in Java erstellt werden.
Das entstehende Programm muss eine festgelegte Schnittstelle bereitstellen. Diese wird am Ende des Praktikums genutzt, um alle entstandenen Programme unter einer gemeinsamen Gui zu vereinen und dem Nutzer zusammen bereitzustellen. Somit trägt jeder Teilnehmer einen Teil zum Gesamtprogramm bei. Die Arbeit soll eigenständig erfolgen und den Umgang mit festen Rahmenbedingungen eines Projektes schulen.
In einem gemeinsamen Veranstaltung sollen die (fast) fertig gestellten Programme gegenseitig geprüft und validiert werden. Zum Ende der Veranstaltung erfolgt eine gemeinsame Vorstellung der implementierten Algorithmen.

Anforderungen

• Literaturrecherche
• umfassende Algorithmenbeschreibung (im Html-Format)
• gut dokumentierter Quellcode (Java)
• Javadoc unterstützende Funktions- und Klassenbeschreibungen zur API-Generierung (englisch?!)
• Input-Fehler robuste Parameterprüfung

Termine

wöchentlich Mo 14-16 Uhr im SR 02 006, Geb.106

20.10.08	Übersicht und Themenvergabe
03.11.08	Einführungsvorträge (10-20 min)
24.11.08	HTML Abgabe
15.12.08	Erste Quellcode-Abgabe und -Überprüfung
26.01.09	Vorläufige Quellcode-Abgabe
02.02.09	Validierungstreffen
09.02.09	Endabgabe

Themen

1.) Algorithmen zur exakten Mustersuche

• naive Mustersuche
• Z-Algorithmus
• Knuth-Morris-Pratt-Algorithmus
• Boyer-Moore-Algorithmus

2.) Verfahren zum paarweisen Sequenz-Alignment

• Needleman-Wunsch-Algorithmus
• Waterman-Smith-Beyer-Algorithmus
• Gotoh-Algorithmus
• Smith-Waterman-Algorithmus

3.) Multiples Sequenz-Alignment und Phylogenie/Clustering

• Sum-of-Pairs-Algorithmus
• Feng-Doolittle-Algorithmus
• UPGMA (Unweighted Pair Group Method using Arithmetic mean)
• WPGMA (Weighted Pair Group Method using Arithmetic mean)

Material

• Schnittstellen-API und Quellcode

Literatur

• Peter Clote and Rolf Backofen. Computational Molecular Biology: An Introduction. Jon Wiley & Sons, Chichester, August 2000.
• Richard Durbin, Sean Eddy, Anders Krogh and Graeme Mitchison. Biological sequence analysis - Probabilistic models of proteins and nucleic acids. Cambridge University Press, Cambridge, 1998.
• Dan Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, Cambridge, 1997.