Seite zur VL und Ü Algorithmen und Datenstrukturen für die Bioinformatik (WiSe 05/06)

News + Wichtiges

23.5.2006	Notenschlüssel und Ergebnisse Nachklausur sind online. Details. Einsichtnahme in der Sprechstunde und nach Vereinbarung (in meinem Büro).
24.3.2006	Zu Übungszwecken finden Sie die erste Klausur unter dem Punkt Übungen.
17.3.2006	Notenschlüssel und Ergebnisse Klausur sind online. Details. Einsichtnahme: Montag, 20.3.2006, 16-18 Uhr, in der Sprechstunde und nach Vereinbarung (in meinem Büro).
17.2.2006	Termin Nachklausur: 13. April, 14:00 s.t., HS 005
17.2.2006	Notenschlüssel und Ergebnisse Übung sind online. Details.
14.2.2006	Klausur am Donnerstag: Vorlagen zum Tafelanschrieb (vor Review 1) sind online.
Evaluierung	Ergebnisse. Vielen Dank für die zahlreiche Teilnahme, die konstruktive Kritik wird ernstgenommen. Ich freue mich sehr über die positive Bewertung.
13.2.2006	Die Ergebnisse des 2. Review sind online. Details
9.2.2006	Die Einteilung für die dritte Programmieraufgabe ist online. Die Einteilung entspricht der für P2, Änderungswünsche bitte an mich per e-Mail, Telefon etc. Abgabe am Dienstag, den 14. Februar 2006. Im Wesentlichen gelten die gleichen Hinweise wie bei der ersten und zweiten Programmieraufgabe. Ort der Abgabe ist wieder K23 und K25.
6.2.2006	Review morgen: Vorlagen zum Tafelanschrieb (nach Review 1) sind online.
1.2.2006	Review naechste Woche: Alle Musterlösungen sind online
31.1.2006	Review naechste Woche: Fast alle Musterlösungen sind online
18.1.2006	Die dritte Programmieraufgabe ist online
5.1.2006	Die Einteilung für die zweite Programmieraufgabe ist online. Abgabe am Dienstag, den 10. Januar 2006. Im Wesentlichen gelten die gleichen Hinweise wie bei der ersten Programmieraufgabe. Ort der Abgabe ist wieder K23 und K25.
22.12.2005	Die Ergebnisse des 1. Review sind online. Details
5.12.2005	Der Nikolaus hat die Musterlösungen gebracht.
30.11.2005	Die zweite Programmieraufgabe ist online
21.11.2005	Die Termine und Zeiten für die Reviews und Klausur stehen fest
21.11.2005	Die Abgabe des vierten Übungsblattes kann ausnahmsweise direkt in der Übung erfolgen.
12.11.2005	P1: Einteilung der Zeiten für die Abgabe am Dienstag online: hier.
10.11.2005	P1: es ist auch OK, wenn Sie das Programm auf Ihrem Laptop vorführen oder sich remote irgendwo einloggen.
9.11.2005	P1: Abgabe + Benotung (s. unten)
7.11.2005	Abgabemodalitäten Programmieraufgabe (s. unten)
	Genauere Spezifikation der Programmieraufgabe (s. unten)
28.10.2005	Die Abgabe des zweiten Übungsblattes kann ausnahmsweise direkt in der zweiten Übung (Di, 8. Nov.) erfolgen.
20.10.2005	Organisatorisches siehe unter Punkt Downloads
	Bitte tragen Sie sich in die Mailingliste zur Veranstaltung ein.

Termin und Ort

Vorlesung: Donnerstags 14-16 Uhr, HS 005, Informatik. Beginn: Donnerstag, 20.10.05
Übung: Dienstags, 10-12, 14-16 oder 16-18 Uhr. Anmeldung über die Seite im KVV Informatik. Beginn: Dienstag, 1.11.05
1. Review: Dienstag, 13.12.2005, im großen Hörsaal der Informatik (Takustr. 9), 16 Uhr, Dauer: 1 h
2. Review: Dienstag, 7.2.2006, im großen Hörsaal der Informatik (Takustr. 9), 16 Uhr, Dauer: 1 h
Klausur: Donnerstag, 16.2.2006, im großen Hörsaal der Informatik (Takustr. 9), 16 Uhr, Dauer: 90 min
Nachklausur: Donnerstag, 13.4.2006, im HS005, Informatik (Takustr. 9), 14 Uhr, Dauer: 90 min

Verantwortliche

Dozent:
Gunnar Klau, gunnar at math.fu.berlin.de. Sprechstunde: Donnerstag 16:30 - 17:30 Uhr + open door policy.
Tutoren:
Johanna Ploog, jploog at inf.fu-berlin.de
Konstantin Clemens, zacharov at inf.fu-berlin.de

Anmeldung

Sie müssen sich zu den beiden Veranstaltungen (Vorlesung und Übung) separat anmelden.

Die Anmeldung zur Übung erfolgt über das elektronische Anmeldesystem zur Einteilung in die Übungsgruppen. Der Stand vom 30. November 2005 gilt als verbindliche Anmeldung.
Die Anmeldung zur Vorlesung erfolgt schriftlich in derselben oder in der Sprechstunde. Auch hier ist der Stand vom 30. November entscheidend.

Offizielle Seiten

aldabi05 im KVV Informatik
aldabi05 im KVV FU

Inhalt

Aus dem Vorlesungsverzeichnis:

Die Vorlesung gibt eine Einführung in grundlegende algorithmische Techniken und Datenstrukturen für Strings und Graphen. Dabei stehen bioinformatische Fragestellungen im Vordergrund.

Es geht im Wesentlichen darum, Paradigmen (z. B. Dynamisches Programmieren, Divide-and-Conquer) und Konzepte (z. B. NP-Vollständigkeit, Approximation) kennenzulernen, die in der algorithmischen Bioinformatik eine zentrale Rolle spielen. Diese Paradigmen und Konzepte werden zunächst allgemein vorgestellt und dann anhand von wichtigen bioinformatischen Themen vertieft (z. B. Dynamisches Programmieren -> Sequenzalignment).

Übungen

Elektronische Anmeldung hier. Übungsblätter und Programmieraufgaben:

Erstes Übungsblatt		Musterlösung
Erste Programmieraufgabe (10 Punkte)
Zweites Übungsblatt	Abgabe kann direkt in der Übung erfolgen!	Musterlösung
Drittes Übungsblatt		Musterlösung
Viertes Übungsblatt	Abgabe kann direkt in der Übung erfolgen!	Musterlösung
Fünftes Übungsblatt	Es weihnachtet sehr: Diesmal nur drei Aufgaben.	Musterlösung
Erster Review
Zweite Programmieraufgabe (12 Punkte)	Webseite zu P2
Sechstes Übungsblatt		Musterlösung
Siebtes Übungsblatt	Abgabe: Donnerstag, 12.1.2006, in der Vorlesung	Musterlösung
Achtes Übungsblatt	Abgabe: Dienstag, 24.1.2006, direkt in der Übung	Musterlösung
Dritte Programmieraufgabe (8 Punkte)	Webseite zu P3
Neuntes Übungsblatt	Abgabe: Dienstag, 31.1.2006, direkt in der Übung	Musterlösung
Zweiter Review
Erste Klausur

Zusatzinformationen zu Übungen und Programmieraufgaben

Mehr zur Abgabe und Benotung von P1.
Abgabe. Die Abgabe erfolgt in 10-Minuten-Slots. Sie tragen sich in der Vorlesung am 10.11.2005 in Listen ein, in denen Sie grob angeben können, wann Sie gerne abgeben würden. Falls Sie zur Vorlesung verhindert sind, teilen Sie uns bitte z. B. durch eine e-Mail mit, wann Sie können. Wir machen dann die Feineinteilung und veröffentlichen diese auf diesen Seiten, nämlich hier.
Sie können zur Abgabe auch Ihren eigenen Laptop mitbringen oder sich remote auf einem anderen Rechner einloggen.
Benotung. Wir schauen uns an, ob das Programm läuft, ob es sich übersetzen lässt, ob es auch auf anderen Eingaben funktioniert und ob die Mitglieder der Gruppe verstanden haben, was sie da programmiert haben. Unseren Gesamteindruck drücken wir als Anzahl der Punkte auf einer Skala von 0 (Programm läuft nicht) bis 10 (alles bestens) aus.
Das Programm muss auf den Abgaberechnern compilierbar sein. Es soll in der Lage sein, zwei Sequenzen sowie zwei Indizes einzulesen und ein bestes Alignment und dessen Score auszugeben. (Die Traceback-Phase muss also auch implementiert werden).
Der Code muss bei der Abgabe laufen. Die Abgabe erfolgt an den Rechnern Basel, Freiburg und Pforzheim (Windows) und Hagen, Aachen und Essen (Linux) in den Räumen K23 bzw. K25 im Keller des Informatik-Gebäudes. Probieren Sie vorher aus, ob alles funktioniert und stellen Sie sicher, dass Sie auf Ihre Daten zugreifen können.

Folien

Die Folien werden hier zeitnah zur Verfügung gestellt. Achtung: Die Folien sind kein Skript.

Organisatorisches	Folien	seitensparend
Pairwise alignment (Part I: basics, Needleman-Wunsch)	Folien	seitensparend
Pairwise alignment (Part II: linear space, local)	Folien	seitensparend
Pairwise alignment (Part III: graph-based)	Folien	seitensparend
Pairwise alignment (Part IV: heuristic (FASTA))	Folien	seitensparend
Multiple alignment (Part I: basics)	Folien	seitensparend
Multiple alignment (Part II: complexity)	Folien	seitensparend
Multiple alignment (Part III: approximation & heuristics)	Folien	seitensparend
String matching (Part I: exact matching, no index)	Folien	seitensparend
String matching (Part II: suffix trees, suffix arrays)	Folien	seitensparend
Markov chains and HMMs	Folien	seitensparend

Literatur

Die Folien werden jeweils vor der Vorlesung ins Netz gestellt. Zusätzlich gibt es am Anfang jedes Kapitels eine Liste, in der die Quellen und Hintergrundliteratur zum jeweiligen Thema zu finden sind. Hier sind drei Bücher, die gut als Einführung geeignet sind (diese befinden sich auch im Handapparat der Fachbereichsbibliothek):

Neil C. Jones, Pavel A. Pevzner: An Introduction to Bioinformatics Algorithms. MIT Press, Cambridge, MA, 2004. ISBN 0-262-10106-8
R. Durbin, S. Eddy, A. Krogh, G. Mitchison: Biological sequence analysis. Cambridge University Press, 1998. ISBN 0-521-62971-3
David B. Mount: Bioinformatics. Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press, New York, 2001. ISBN 0-87969-608-7

Interessante Links

Veranstaltung letztes Jahr
Veranstaltung vor zwei Jahren
Online lectures, MPI for Molecular Genetics
Eddy S.R. (2004a). What is dynamic programming? Nature Biotechnology 22:909-910
Seite zum Millenium problem "P versus NP". Auf der Seite ist auch ein sehr schönes Video einer Vorlesung zu P vs. NP von Vijaya Ramachandran. Wenn der Stream nicht funktioniert: Hier ist das File (Achtung, fast 200 MB)

Gunnar W. Klau

Last modified: Fri Mar 24 12:02:33 MET 2006