Algorithmen auf Sequenzen Algorithms on Sequences
This page is available in German only.
Aktuelle Hinweise
Die Wiederholungsklausur fand am Donnerstag, den 18.04.24
statt.
Die Semestralklausur fand am Mittwoch, den 28.02.24
statt.Informationsblatt 2 ist in Moodle
verfügbar.
Für die Teilnahme am Modul und an der Modulprüfung war
eine Anmeldung 26. Oktober 2023 sowie eine Anmeldung
zum zugehörigen Moodle-Kurs bis
zum 31. Oktober 2023 erforderlich.
Es wird dringend empfohlen, sich bereits in der vorlesungsfreien
Zeit inhaltlich auf die Vorlesung vorzubereiten, für Details
hierzu siehe Voraussetzungen und Vorbereitungen .
Die aktuelle Version 9.28 vom 06.02.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:
Mo 10ct–12 Theresienstr. 39, B039 Mi 10ct–12 Theresienstr. 39, B039
Übungen:
2 SWS Übung zur Vorlesung
Mi
12st–14
Theresienstr. 39, B039
Material
Das Skript
wird im Laufe der Vorlesung aktualisiert.
Es gibt auch einen zugehörigen
Moodle-Kurs
mit weiterem Material.
Voraussetzungen und Vorbereitungen
Voraussetzungen:
Stoff des Bioinformatik- bzw. Informatik-Grundstudiums. Der
erfolgreiche Besuch der Veranstaltung Algorithmische
Bioinformatik I und II ist empfehlenswert.
Vorbereitungen:
Es wird dringend empfohlen, bereits vor Vorlesungsbeginn die Inhalte
von Algorithmische Bioinformatik I und II
(insbesondere zu Suffix-Bäumen und Approximierbarkeit),
[Grundlagen:] Algorithmen und Datenstrukturen
sowie Formale Sprachen und Komplexität/Theoretische Informatik
(insbesondere zur Algorithmik und NP-Vollständigkeit) zu wiederholen.
Inhalt der Vorlesung
Lernergebnis:
Die Teilnehmer sind in der Lage Problemstellungen auf Sequenzen für
einen algorithmischen Zugang zu modellieren, die algorithmische
Komplexität des Problems zu bestimmen und einzuordnen, Algorithmen
für die Lösung zu entwerfen und zu analysieren.
Themen:
Die Vorlesung behandelt die folgende Themen:
Optimal Scoring Subsequences
Suffix Trees Revisited
Repeats
Interludium: LCA-Queries und RMQ
Suffix Arrays
Genome Rearrangements
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.
Details zur Modulprüfung werden jeweils rechtzeitig bekannt
gegegben.
Die Semestralklausur fand am Mittwoch, den
28. Februar 2024 statt.
Für Details zur Modulprüfung siehe das
Informationsblatt 2 in Moodle.
Die Wiederholungsklausur fand
am Donnerstag, den 18. April 2024 statt.
Für Details siehe das Informationblatt 3 in Moodle.
Informationsblätter
Übungsblätter
Literatur zur Vorlesung
S. Aluru (Ed.):
Handbook of Computational Molecular Biology ,
Chapman and Hall/CRC, 2006.
G. Fertin, A. Labarre, I. Rusu, E. Tannier, S. Vialette:
Combinatorics of Genome Rearrangements , MIT Press, 2009.
D. Gusfield:
Algorithms on Strings, Trees, and Sequences: Computer Science and
Computational Biology , Cambridge University Press, 1997.
V. Heun:
Algorithmische Bioinformatik ,
Skripten ,
2001-2015.
S. Kurtz:
Lecture
Notes for Foundations of Sequence Analysis
V. Mäkinen, D. Belazzougui, F. Cunial, A.I. Tomescu:
Genome-Scale Algorithm Design: Biological Sequence Analysis in
the Era of High-Throughput Sequencing ,
Cambridge University Press, 2015
E. Ohlebusch:
Bioinformatics Algorithms ,
Oldenbusch Verlag, 2013.
Sowie Originalliteratur (siehe Skript).
