Sie entspricht Master-Modul INF-MSc-606, kann aber ggf. auch als INF-MSc-603 angerechnet werden; bitte frühzeitig mit dem Veranstalter absprechen.
Sie gehört in die SpGs 4,6,7 nach DPO'01 und ist wahlweise als 2V+2Ü = 6 LP (Master) oder 3V+1Ü (Diplom) anrechenbar.
Termin und Raum: ---
Inhalt (Vorlesungskommentar)
Wir behandeln verschiedene Algorithmische Aspekte der Bioinformatik,
allerdings ohne Probleme, die in der Vorlesung "Algorithmen auf
Sequenzen" behandelt werden. Es ist sinnvoll, bei Interesse beide
Veranstaltungen zu besuchen.
Beispiele sind:
- Genomsequenzierung und -assemblierung
- Rekonstruktion Phylogenetischer Bäume
- Genom-Dynamik (Umordnungsprobleme)
- Genexpressions-Analyse mit Microarrays
- Algorithmen der Massenspektrometrie
- Analyse mehrdimensionaler Spektrometriedaten
- Algorithmische Probleme des DNA-Origami
Die Vorlesung wird von praktischen und theoretischen Übungsaufgaben begleitet, deren Bearbeitung wichtig für ein richtiges Verständnis des Stoffs ist. Die Übungen finden im selben Raum unmittelbar im Anschluss an die Vorlesung statt.
Im Anschluss an diese Vorlesung besteht bei Begabung und Interesse die Möglichkeit, in diesem Bereich eine Diplomarbeit zu schreiben.
Literatur und Material
Durbin, Eddy, Krogh & Mitchison:Biological Sequence Analysis (Probabilistic Models of Proteins and Nucleic Acids), 1. Auflage von 1998
Cambridge University Press
http://www.amazon.de/Biological-Sequence-Analysis-Probabilistic-Proteins/dp/0521629713
Pavel Pevzner
Computational Molecular Biology - An Algorithmic
Approach
MIT Press
Neil Jones and Pavel Pevzner
An
Introduction to Bioinformatics Algorithms
MIT Press
Hans-Joachim
Böckenhauer and Dirk Bongartz
Algorithmische Grundlagen der
Bioinformatik - Modelle, Methoden und Komplexität
Teubner
David Mount
Bioinformatics (Sequence and Genome Analysis), 2. Auflage von 2004
Cold Spring Harbor Laboratory Press
http://www.amazon.de/Bioinformatics-Sequence-Analysis-David-Mount/dp/0879697121
Skript
Ein Skript wird parallel zur Vorlesung erstellt. Aktuelle Version siehe unten.Zeitplan Sommersemester 2010
Die Vorlesung findet statt: Mo 10-12 in OH14, R104 und Do 08-10 in OH14, R104.Die Übungen sind in die Vorlesung integriert. Es ist dringend empfehlenswert, sich an den Übungen aktiv zu beteiligen und die Aufgaben zu bearbeiten!
Dieser Zeitplan wird im Verlauf des Sommersemesters aktualisiert.
Aktuelle Version des Skripts.
| Mo
12.04. | Organisatorisches. Übersicht. DNA, RNA, Proteine. Genetischer Code. Metabolite. |
| Do 15.04. | Genomprojekte früher und heute. Lander-Waterman-Modell. Das PDP-Problem, Algorithmus von Skiena. Übungsblatt 1 (Besprechung am 22.04.) |
| Mo 19.04. | Das DDP-Problem. NP-Vollständigkeit des DDP-Problems. Kartierung durch Hybridisierung (Consecutive Ones Problem) |
| Do 22.04. | Übung 1 |
| Mo 26.04. | pq-Bäume und eine effiziente Lösung des Consecutive Ones Problems. Übungsblatt 2 (Besprechung am 06.05.) |
| Do 29.04. | Microarrays und ihre
Anwendungen. Folien. Low-level-Analyse von Microarray-Daten. |
| Mo 03.05. | Sequencing by Hybridization (SBH): Algorithmen und Kombinatorik. Übungsblatt 3 (Besprechung am 20.05.) |
| Do 06.05. | Übung 2 |
| Mo
10.05. | Einführung in die Phylogenetik. Anzahl der phylogenetischen Bäume, Einteilung der Methoden. |
| Do 13.05. | -- Himmelfahrt -- |
| Mo
17.05. | Parsimony-Methoden: kleines und großes Parsimony-Problem. Sankoff- und Fitch-Algorithmus. Branch-and-Bound-Idee. |
| Do 20.05. | Übung 3 (zu SBH) |
| Mo 24.05. | --
Pfingstmontag -- |
| Do 27.05. | Minimum-Flip-Probleme und ein ILP zur Lösung. |
| Mo 31.05. | Distanzbasierte Methoden: UPGMA. Übungsblatt 4 (zur Phylogenetik, Besprechung am 10.06.) |
| Do 03.06. | -- Fronleichnam -- |
| Mo 07.06. | Neighbor Joining (NJ). |
| Do 10.06. | Übung 4 (zur Phylogenetik) |
| Mo 14.06. | Neighbor Joining auf fast additiven Distanzen Übungsblatt 5 (Besprechung am 24.06.) |
| Do
17.06. | Sichtbarkeit, Fast Neighbor Joining (FNJ) |
| Mo
21.06. | (Stillarbeit zu technischen Lemmas, FNJ) |
| Do 24.06. | Übung 5 |
| Mo 28.06. | Genom-Umordnungen, Genomgraph: Adjazenzen und Telomere Umordnungsoperationen auf Genomen, insbesondere DCJ-Operation Genomdistanzen, insbesondere DCJ-Distanz. |
| Do 01.07. | Berechnung
der DCJ-Distanz über Adjazenzgraphen. Übungsblatt 6 (Besprechung am 08.07.) |
| Mo 05.07. | Einführung in die Massenspektrometrie. Massenzerlegungsproblem. |
| Do 08.07. | Übung 6 (DCJ, MS) |
| Mo 12.07. | Selbststudium: Sorting by Block Interchanges. Fragen dazu sind im Skript im entsprechenden Abschnitt. Web server (BiBiServ, Bielefeld) zum Ausprobieren und Hinweise zur Implementierung. Material: Dissertation von D.A. Christie, Kapitel 4.1 bis 4.4 (nur ein paar Seiten) |
| Do 15.07. | Theoretische Massenspektren. Peptide
Mass Fingerprinting. |
| Mo 19.07. | Einführung in die
Ionenmobilitätsspektrometrie. Low-Level-Analyse,
Peakmodelle. Peakbestimmung in IMS-Spektren. EM-Algorithmus. |
| Do 22.07. | Übung 7, Abschluss. |
Eventuell weitere Themen, je nach Zeit und Interesse, z.B.:
- RNA-Sekundärstruktur. Einfache Vorhersage: Nussinov-Algorithmus. Komplexere RNA-Energiemodelle