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, 13.03.2020 und nach Vereinbarung. Zur Anmeldung ist kein Leistungsnachweis erforderlich. Informationen. Anmeldeformular

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.
  Übung: Blatt 6
Di 17.12. Probabilistische arithmetische Automaten; Anwendungen von PAAs.
  Übung: Blatt 7, Material: Corynebacterium diphtheriae gzipped FASTA
(Weihnachts-)  
(ferien)  
Di 07.01. Probabilistische arithmetische Automaten: Konstruktion über DAAs
  Übung: Blatt 8
Di 14.01. Phylogenetik: Bäume, Anzahlen, Perfekte Phylogenien
  Übung: Blatt 9
Di 21.01. Phylogenetik: Merkmalsbasierte Methoden: Maximum Parsimony, Minimum Flip
  Übung: Blatt 10
Di 28.01. Phylogenetik: Distanzbasierte Methoden: Hierarchisches Clustern (UPGMA), Neighbor Joining
  Übung: Blatt 11
Mi 12.02. Phylogenetik: Details zu Neighbor Joining (OH14/202!)
  Besprechung von Blatt 11; kein neues Blatt.

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.