Algorithmen auf SequenzenAlgorithms on Sequences

This page is available in German only.

Aktuelle Hinweise

Das Modul findet in Form digitaler Lehre statt.
Die aktuelle Version 8.20 vom 10.01.21 des Skripts ist verfügbar.
Die vollständige Version 7.32 vom 17.02.19 des Skripts ist verfügbar.

Alte Hinweise

Für die Teilnahme am Modul und an der Modulprüfung ist eine Anmeldung bis zum 26. Oktober 2020 sowie die Anmelduung am zugehörigen Moodle-Kurs erforderlich.
Organisatorische und administrative Details werden in der ersten Übung am 3. November um 12 Uhr s.t. per Videokonferenz besprochen. Die Zugangsdaten werden den Angemeldeten per E-Mail mitgeteilt.
Es wird dringend empfohlen, sich bereits in der vorlesungsfreien Zeit inhaltlich auf die Vorlesung vorzubereiten, für Details hierzu siehe Voraussetzungen und Vorbereitungen.

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	digitale Lehre
Do	10ct–12	digitale Lehre

Übungen:

2 SWS Übung zur Vorlesung

Assistentin: Volker Heun

12st–14

per Videokonferenz

Material

Das Skript wird im Laufe der Vorlesung aktualisiert.

Weiteres Material ist im zughörigen Moodle-Kurs und in LMUcast (im Moodle-Kurs verlinkt) zur Verfügung gestellt.

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 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 zur Verfügung gestellt.

Modulprüfung

Details zur Modulprüfung werden noch bekannt gegegben.

Die Modulprüfung findet voraussichtlch in Präsenz als schriftliche Prüfung, der Semestralklausur, Mitte/Ende Februar statt.

Für die Teilnahme an der Modulprüfung ist eine Anmeldung zum Modul (zur Vorlesung und zu den Übungen) bis zum 26.10.2020 sowie die Anmelduung am zugehörigen Moodle-Kurs erforderlich.

Informationsblätter

Informationblatt	vom
Informationsblatt 1	25.10.

Übungsblätter

Übungsblatt	vom	Abgabe bis
Übungsblatt 1	03.11.20	13.11.20
Übungsblatt 2	10.11.20	20.11.20
Übungsblatt 3	17.11.20	27.11.20
Übungsblatt 4	24.11.20	04.12.20
Übungsblatt 5	01.12.20	11.12.20
Übungsblatt 6	08.12.20	18.12.20
Übungsblatt 7	15.12.20	08.01.21
Übungsblatt 8	22.12.20	15.01.21
Übungsblatt 9	12.01.21	22.01.21

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, Chapter 4, 2001.
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).