Vorlesung “Algorithmische Bioinformatik”

  • Die Vorlesung entspricht Master-Modul INF-MSc-606. Sie ist als 2V+2Ü = 6 LP (Master) oder 3V+1Ü (Diplom, SpGs 4,6,7) anrechenbar. Weitere allgemeine Informationen: unterhalb des Zeitplans.
  •  Aktuelles Skript (2017).

Wintesemester 2017/18

Vorlesung: Do 8:30 – 10:00 in OH14/304
Übung: Do 12:15 – 13:45 in OH14/304

Do 12.10. Aus organisatorischen Gründen beginnt die Vorlesung erst am 19.10.
Do 19.10. Vorlesung: Organisatorisches. Übersicht.
Grundlagen der molekularen Zellbiologie (Folien).
Simulation von Zufallssequenzen, Alias-Methode.
Übung: Blatt 1. Organisatorisches, Übungsbetrieb.
Material: Gene von E. coli (im FASTA-Format)
Do 26.10. Die Veranstaltung (Vorlesung+Übung) fällt wegen Krankheit leider aus.
Do 02.11. Vorlesung: Textmodelle für biologische Sequenzen.
Rechnen mit kleinen Wahrscheinlichkeiten.
Berechnung von Textwahrscheinlichkeiten. Simulation von Zufallstexten.
Parameterschätzung in Textmodellen.
Markov-Modelle fester und variabler Ordnung,
Übung: Blatt 2
Do 09.11. Vorlesung: allgemeine Textmodelle mit endlichem Gedächtnis.
Definition von HMMs, Algorithmen für HMMs.
Übung: Blatt 3
Do 16.11. Vorlesung: Algorithmen für HMMs.
Beispiele für HMM-Anwendungen.
Übung: Blatt 4
Do 23.11. Vorlesung: HMM-Training (Baum-Welch). HMM-Erweiterungen: Stumme Zustände, Dauermodellierung.
Übung: Blatt 5
Do 30.11. Vorlesung: Positions-Gewichts-Matrizen (PWMs): Definition, Algorithmen, Visualisierung.
Übung: Blatt 6
Do 07.12. Vorlesung: Positions-Gewichts-Matrizen (PWMs): Definition, Algorithmen, Visualisierung.
Übung:
Do 14.12. Vorlesung: Probabilistische Arithmetische Automaten (PAAs): Definition, Algorithmen
Übung:
Do 21.12. Vorlesung: Probabilistische Arithmetische Automaten (PAAs): Erweiterungen, Anwendungen
Übung:
Do 11.01. Vorlesung: Phylogenetische Bäume: Grundlagen, Perfekte Phylogenien
Übung:
Do 18.01. Vorlesung: Phylogenetische Algorithmen: Perfekte Phylogenien, Maximum Parsimony
Übung:
Do 25.01. Vorlesung: Phylogenetische Algorithmen: Minimum Flip; Idee der distanzbasierten Verfahren
Übung:
Do 01.02. Vorlesung: Phylogenetische Algorithmen: UPGMA, Neighbor Joining (distanzbasiert)
Übung:
Do 08.02. Vorlesung: Phylogenetische Algorithmen: Schnelles Neighbor Joining
Übung:

Inhalte der Vorlesung

Wir behandeln verschiedene algorithmische Aspekte der Bioinformatik, allerdings ohne Probleme, die in der Vorlesung “Algorithmen auf Sequenzen” behandelt werden. Es ist sinnvoll, aber nicht notwendig, bei Interesse beide Veranstaltungen zu besuchen.

Themenbereiche sind:

  • statistische Modelle für biologische Sequenzen
  • Modellierung von Protein- und Genfamilien mit Hidden Markov Modellen
  • Bewertung biologischer Motive mit probabilistischen arithmetischen Automaten
  • Algorithmen zur Rekonstruktion phylogenetischer Bäume

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 Abschlussarbeit zu schreiben.

Literatur und Material

Durbin, Eddy, Krogh & Mitchison:
Biological Sequence Analysis (Probabilistic Models of Proteins and Nucleic Acids), 1. Auflage von 1998
Cambridge University Press
http://www.amazon.de/Biological-Sequence-Analysis-Probabilistic-Proteins/dp/0521629713

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 Verlag

David Mount
Bioinformatics (Sequence and Genome Analysis), 2. Auflage von 2004
Cold Spring Harbor Laboratory Press
http://www.amazon.de/Bioinformatics-Sequence-Analysis-David-Mount/dp/0879697121


Ältere Ausgaben der Vorlesung

Sommersemester 2016

Do 14.04. Vorlesung: Organisatorisches. Übersicht.
Grundlagen der molekularen Zellbiologie (Folien).
Simulation von Zufallssequenzen, Alias-Methode.
Übung: Organisatorisches, Übungsbetrieb.
Übungsblatt 1. Material zu Blatt 1: Gene von E. coli (im FASTA-Format)
Do 21.04. Vorlesung: Textmodelle für biologische Sequenzen.
Rechnen mit sehr kleinen Wahrscheinlichkeiten.
Berechnung von Textwahrscheinlichkeiten. Simulation von Zufallstexten.
Parameterschätzung in Textmodellen.
Übung: Besprechung von Blatt 1. Ausgabe von Übungsblatt 2.
Do 28.04. Vorlesung: Markov-Modelle fester und variabler Ordnung,
allgemeine Textmodelle mit endlichem Gedächtnis, Definition HMMs
Übung: Besprechung von Blatt 2. Ausgabe von Übungsblatt 3.
Do 05.05. Feiertag (Himmelfahrt)
Do 12.05. Vorlesung: Beispiele für HMM-Anwendungen,
Algorithmen für HMMs (Viterbi, Forward)
Übung: Besprechung von Blatt 3. Musterlösung zu Aufgabe 3.3. Ausgabe von Übungsblatt 4.
Do 19.05. Vorlesung: Algorithmen für HMMs (Forward-Backward).
Erweiterungen: Stumme Zustände, Dauermodellierung, mixture models.
Bemerkungen zum Training vom HMMs.
Übung: Besprechung von Blatt 4. Ausgabe von Übungsblatt 5.
Do 26.05. Feiertag (Fronleichnam)
Do 02.06. Vorlesung: Positions-Gewichts-Matrizen (PWMs): Definition, Algorithmen, Visualisierung.
Übung: Besprechung von Blatt 5. Ausgabe von Übungsblatt 6.
Do 09.06. Vorlesung: Probabilistische Arithmetische Automaten (PAAs): Definition, Algorithmen
Übung: Besprechung von Blatt 6. Ausgabe von Übungsblatt 7.
Do 16.06. Vorlesung: Probabilistische Arithmetische Automaten (PAAs): Erweiterungen, Anwendungen
Übung: Besprechung von Blatt 7. Ausgabe von Übungsblatt 8.
Do 23.06. Vorlesung: Phylogenetische Bäume: Grundlagen, Perfekte Phylogenien
Übung: Besprechung von Blatt 8. Ausgabe von Übungsblatt 9.
Do 30.06. Vorlesung: Phylogenetische Algorithmen: Perfekte Phylogenien, Maximum Parsimony
Übung: Besprechung von Blatt 9 (Lösung der Aufgabe 9.2 von Jens Schulze in R). Ausgabe von Übungsblatt 10.
Do 07.07. Vorlesung: Phylogenetische Algorithmen: Minimum Flip; Idee der distanzbasierten Verfahren
Übung: Besprechung von Blatt 10. Ausgabe von Übungsblatt 11.
Do 14.07. Vorlesung: Phylogenetische Algorithmen: UPGMA, Neighbor Joining (distanzbasiert)
Übung: Besprechung von Blatt 11. Ausgabe von Übungsblatt 12.
Do 21.07. Vorlesung: Phylogenetische Algorithmen: Schnelles Neighbor Joining
Übung: Besprechung von Blatt 12. Zusammenfassung.

Noch ältere Ausgaben der Vorlesung