Algorithmische Bioinformatik: Bäume und Graphen Algorithms Bioinformatics: Trees and Graphs
This page is available in German only.
Aktuelle Hinweise
Für die Teilnahme am Modul und an der Modulprüfung
ist eine
Anmeldung
bis zum
25. April 2024 erforderlich.
Das aktualisierte Informationsblatt 1 ist
verfügbar.
Es wird dringend empfohlen, sich bereits in
der vorlesungsfreien Zeit inhaltlich auf die Vorlesung
vorzubereiten, für Details hierzu siehe
Voraussetzungen und
Vorbereitungen
Weitere Lehrmaterialien sind im zugehörigen
Moodle-Kurs
verfügbar (die Aufnahme in den Moodle-Kurs erfolgt nach Ende
der Anmeldung).
Die Version 8.04 vom 25.04.24 des
Skripts
ist verfügbar.
Allgemeine Informationen
Dozent:
Volker Heun Umfang und Hörerkreis:
4 SWS Vorlesung + 2 SWS Tutorübung / 9 ECTS-Punkte
Vorlesung für Studierende der Bioinformatik im Bereich Bioinformatik
Vorlesung für Studierende der Informatik
Zeit und Ort:
Di 10ct–12 Theresienstr. 39, B132 Do 10ct–12 Theresienstr. 39, B132
Übungen:
2 SWS Übung zur Vorlesung
Do
12st–14
Theresienstr. 39, B132
Material
Voraussetzungen und Vorbereitung
Stoff des Bioinformatik bzw. Informatik Grundstudiums. Der erfolgreiche
Besuch der Veranstaltung Algorithmische Bioinformatik I ist
empfehlenswert.
Es wird dringend empfohlen, die Inhalte von
Algorithmische Bioinformatik I ,
Algorithmische Bioinformatik II (insbesondere zur
Approximierbarkeit) und
[Grundlagen:] Algorithmen und Datenstrukturen (insbesondere zu
Union-Find, Priority Queues, Fibonacci-Heaps) zu wiederholen.
Inhalt der Vorlesung
Lernergebnis:
Die Teilnehmer sind in der Lage, biologische Problemstellungen, wie die
Erstellung von Phylogenien und Linearisierung von genomischen Gruppen,
mithilfe von Graphen und speziell Bäumen geeignet zu modellieren,
damit sie einem automatisierten Lösungsverfahren zugänglich
sind, die algorithmische Komplexität (bzgl. der
Komplexitätsklassen P, NP, NPC, PSPACE, EXPTIME, etc.) des
zughörigen Problems einzuordnen, Algorithmen für deren Lösung
zu entwerfen und diese im Hinblick auf deren Effektivität
(Korrektheit) und Effizienz (bzgl. Laufzeit und Speicherplatzverbrauch)
zu analysieren.
Themen:
Die Vorlesung behandelt voraussichtlich die folgende Themen:
Evolutionary Trees
binäre perfekte Phylogenie
allgemeine perfekte Phylogenie
perfekte Phylogenie mit zwei Merkmalen
ultrametrische Bäume
additive Bäume
kompakt additive Bäume
Exkurs: Priority Queues und Fibonacci-Heaps
Sandwich- und Approximationsprobleme
Splits und Splits-Graphen
Physical Mapping
PQ-Bäume und Consecutive Ones Property
PQR-Bäume, PC-Bäume und andere Varianten
Exkurs: Union-Find-Datenstrukturen
Intervall-Graphen und parametrisierte Sandwich-Probleme
Eine aktuelle Inhaltsangabe wird im Laufe der Vorlesung im
zugehörigen
Moodle-Kurs zur Verfügung gestellt.
Modulprüfung
Die Modulprüfung findet als schriftliche Prüfung, der
Semestralklausur, statt.
Die Semestralklausur ist nach derzeitigen Plaungen für den Zeitraum
18. mit 26. Juli oder 5. mit 14. August vorgesehen
(Änderungen sind möglich).
Für die Teilnahme an der Modulprüfung ist eine
Anmeldung
zur Vorlesung und den Übungen bis zum 25.04.2024 sowie im
zugenögigen Moodle-Kurs erforderlich.
Informationsblätter
Übungsblätter
Literatur zur Vorlesung
P. Clote, R. Backofen:
Computational Molecular Biology - An Introduction ,
Wiley, 2000.
J. Felsenstein:
Inferring Phylogenies ,
Sinauer Associates, 2004.
D. Gusfield:
Algorithms on Strings, Trees, and Sequences: Computer Science and
Computational Biology ,
Cambridge University Press, 1997.
D. Huson, R. Rupp, C. Scornavacca:
Phylogenetic Networks: Concepts, Algorithms and Applications ,
Cambridge University Press, 2010.
V. Heun:
Algorithmische Bioinformatik I/II/III ,
Skriptum ,
2001-2005
M. Nei, S. Kumar:
Molecular Evolution and Phylogenetics ,
Oxford University Press, 2000.
Marco Salemi, Anne-Mieke Vandamme:
The Phylogenetic Handbook: A Practical Appoach to DNA and
Protein Phylogeny ,
Cambridge University Press, 2003
C. Semple, M. Steel:
Phylogenetics ,
Oxford Lecture Series in Mathematics and its Applications, Vol. 24.
Oxford University Press, 2003.
