Vorlesung “Algorithmische Bioinformatik”

Wintersemester 2019/20

Vorlesung: Di 08:30-10:00 in OH12 / 1.056
Übungen: Di 12:15-13:45 in OH12 / 1.055
Modul: INF-MSc-606, Forschungsbereich Algorithmen und Komplexität
Material: Skript-Entwurf
Prüfungen: 6 CP; mündlich nach Vereinbarung. Zur Anmeldung ist kein Leistungsnachweis erforderlich.

Di 08.10. Einführung, Simulation von Zufallssequenzen
  Übung: Blatt 1. Material: Gene von E. coli. Lösung: Python
Di 15.10. Textmodelle: M0, M1, Mk, Markovmodelle variabler Ordnung.
  Übung: Blatt 2
Di 22.10. Achtung! Um 08:30 keine Vorlesung. Die Vorlesung wird 12:15-13:45 in OH12/1.055 von Jens Zentgraf vertreten.
Allgemeine Textmodelle; Rechnen mit kleinen Wahrscheinlichkeiten.
  Keine Übung!
Di 29.10. Textmodelle: Parameterschätzung. Einführung in Hidden-Markov-Modelle. Material: ML- und MAP-Schätzung der Erfolgswahrscheinlichkeit beim Münzwurf
  Übung: Blatt 3
Di 05.11. Hidden Markov Modelle: Algorithmen (Forward, Viterbi)
  Übung: Blatt 4
Di 12.11. Hidden Markov Modelle: Algorithmen (Forward-Backward), Training
  Übung: Blatt 5
Di 19.11. fällt aus; keine Vorlesung; keine Übung
Di 26.11. HMMs: Erweiterungen. Artikel zur Verweildauermodellierung. Kein neues Übungsblatt.
Di 03.12. fällt wegen Krankheit aus!
Di 10.12. Motivmodelle, insbesondere PWMs.
  Blatt 6
Di 17.12. Probabilistische arithmetische Automaten; Anwendungen von PAAs.
  Blatt 7
(Ferien)  
Di 07.01. Phylogenetik: Merksmalsbasierte Methoden
Di 14.01. Phylogenetik: Merkmalsbasierte Methoden
Di 21.01. Phylogenetik: Distanzbasierte Methoden
Di 28.01. Phylogenetik: Distanzbasierte Methoden

Inhalt (Vorlesungskommentar)

Wir behandeln verschiedene algorithmische Aspekte der Bioinformatik. Ein vorausgegangener Abschluss der Bachelor-Vorlesung “Algorithmen auf Sequenzen“ ist hilfreich.

Themenbereiche sind:

  • statistische Modelle für biologische Sequenzen (und andere Texte)
  • Data Mining in Genomdaten (z.B. Motivsuche)
  • Rekonstruktion phylogenetischer Bäume
  • Genom-Dynamik (Umordnungsprobleme)

Die Vorlesung wird von praktischen und theoretischen Übungsaufgaben begleitet, deren Bearbeitung wichtig für ein genaues Verständnis des Stoffs ist. Im Anschluss an diese Vorlesung besteht bei Interesse die Möglichkeit, in diesem Bereich eine Masterarbeit zu schreiben.

Literatur

  • Durbin, Eddy, Krogh & Mitchison:
    Biological Sequence Analysis (Probabilistic Models of Proteins and Nucleic Acids)
    Cambridge University Press
  • 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)
    Cold Spring Harbor Laboratory Press
  • Weitere Originalliteratur (wissenschaftliche Aufsätze, “paper”), die im Lauf der Vorlesung bekannt gegeben wird.