Vorlesung "Algorithmische Bioinformatik"

Lehre‎ > ‎

Vorlesung "Algorithmische Bioinformatik"

Diese Spezialvorlesung von Prof. Sven Rahmann findet im SoSe 2013 statt.

Ein Vorlesungs- und Zeitplan findet sich weiter unten.
Die Vorlesung entspricht Master-Modul INF-MSc-606, kann aber ggf. auch als INF-MSc-603 angerechnet werden; bitte frühzeitig mit dem Veranstalter absprechen. Sie gehört in die SpGs 4,6,7 nach DPO'01 und ist wahlweise als 2V+2Ü = 6 LP (Master) oder 3V+1Ü (Diplom) anrechenbar.

Termine und Räume im SoSe 2013:
Achtung: dauerhafte Raumänderung nach OH14/304! Die Übung am 11.04. findet statt!

Vorlesung: Mi 8-10, OH14/304.

Übung: Do 8-10, OH14/304.

Diese Einteilung ist relativ beliebig, Vorlesung und Übung bilden zusammen eine Einheit!

Inhalt (Vorlesungskommentar)

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
Genomsequenzierung und -assemblierung
Rekonstruktion phylogenetischer Bäume
Genom-Dynamik (Umordnungsprobleme)
Algorithmen der Massenspektrometrie
Algorithmische Probleme des DNA-Origami
Clustering sehr großer biologischer Datenmengen

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 Diplomarbeit 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

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

Skript

Ein Skript wird parallel zur Vorlesung erstellt.

Aktuelle Version (2013).

Zeitplan Sommersemester 2013

Die Vorlesung und Übung findet jeweils statt: Mi 8:30-10:00 OH14/304, Do 8:30-10:00 OH14/304. (Raumänderung!)

Mi 10.04.	Organisatorisches. Übersicht. Übungsbetrieb. Simulation von Zufallssequenzen, Alias-Methode.
Do 11.04.	Die Übung findet statt, und zwar in OH14/304 ! Übungsblatt 1, Präsenzübungen, Hilfestellungen. Material: Gene von E. coli (3.8 MB fasta), Python-Code aus der Übung (mit read_fasta). Hinweis: Der Code ist mit Python 3.2 erstellt, er läuft so nicht unter 2.x! Python gibt es unter www.python.org.
Mi 17.04.	Modelle für biologische Sequenzen (DNA, RNA, Proteine): Gleichverteilung, i.i.d, Markov, endliches Gedächtnis. Berechnung von Wahrscheinlichkeiten.
Do 18.04.	Übungsblatt 2. Besprechung von Blatt 1.
Mi 24.04.	HMMs: Forward-Variablen, Forward-Algorithmus, Viterbi-Algorithmus
Do 25.04.	Übungsblatt 3. Besprechung von Blatt 2.
Mi 01.05.	-- Tag der Arbeit --
Do 02.05.	Übungsblatt 4. Besprechung von Blatt 3.
Mi 08.05.	HMMs: Posterior decoding: Forward-Backward-Algorithmus. Ergänzungen: Stumme Zustände, Verweildauer in Zuständen. Anwendungen: Proteinfamilien, Gene finding.
Do 09.05.	-- Christi Himmelfahrt --
Mi 15.05.	Positions-Gewichts-Matrizen (PWMs), Modellierung von Transkriptionsfaktorbindestellen
Do 16.05.	Übungsblatt 5. Besprechung von Blatt 4.
Mi 22.05.	Probabilistische arithmetische Automaten (PAAs). Berechnungen auf stochastischen Sequenzen. Anwendung: Motiv-Statistiken
Do 23.05.	Übungsblatt 6. Besprechung von Blatt 4 (CDS finding) und Blatt 5.
Mi 29.05.	PAAs, Anwendung: Optimierung von Pyrosequencing
Do 30.05.	-- Fronleichnam --
Mi 05.06.
Do 06.06.
Mi 12.06.
Do 13.06.
Mi 19.06.
Do 20.06
Mi 26.06.
Do 27.06.
Mi 03.07.
Do 04.07.
Mi 10.07.
Do 11.07.
Mi 17.07.
Do 18.07.

Weitere Themen:

Evolutionäre Markovprozesse, Phylogenetische Algorithmen, RNA-Sekundärstruktur (stochastische kontextfreie Grammatiken), Genome Rearrangements, DNA-Sequenz-Design.

Zeitplan Sommersemester 2010

Die Vorlesung findet statt: Mo 10-12 in OH14, R104 und Do 08-10 in OH14, R104.
Die Übungen sind in die Vorlesung integriert. Es ist dringend empfehlenswert, sich an den Übungen aktiv zu beteiligen und die Aufgaben zu bearbeiten!

Mo 12.04.	Organisatorisches. Übersicht. DNA, RNA, Proteine. Genetischer Code. Metabolite.
Do 15.04.	Genomprojekte früher und heute. Lander-Waterman-Modell. Das PDP-Problem, Algorithmus von Skiena. Übungsblatt 1 (Besprechung am 22.04.)
Mo 19.04.	Das DDP-Problem. NP-Vollständigkeit des DDP-Problems. Kartierung durch Hybridisierung (Consecutive Ones Problem)
Do 22.04.	Übung 1
Mo 26.04.	pq-Bäume und eine effiziente Lösung des Consecutive Ones Problems. Übungsblatt 2 (Besprechung am 06.05.)
Do 29.04.	Microarrays und ihre Anwendungen. Folien. Low-level-Analyse von Microarray-Daten.
Mo 03.05.	Sequencing by Hybridization (SBH): Algorithmen und Kombinatorik. Übungsblatt 3 (Besprechung am 20.05.)
Do 06.05.	Übung 2
Mo 10.05.	Einführung in die Phylogenetik. Anzahl der phylogenetischen Bäume, Einteilung der Methoden.
Do 13.05.	-- Himmelfahrt --
Mo 17.05.	Parsimony-Methoden: kleines und großes Parsimony-Problem. Sankoff- und Fitch-Algorithmus. Branch-and-Bound-Idee.
Do 20.05.	Übung 3 (zu SBH)
Mo 24.05.	-- Pfingstmontag --
Do 27.05.	Minimum-Flip-Probleme und ein ILP zur Lösung.
Mo 31.05.	Distanzbasierte Methoden: UPGMA. Übungsblatt 4 (zur Phylogenetik, Besprechung am 10.06.)
Do 03.06.	-- Fronleichnam --
Mo 07.06.	Neighbor Joining (NJ).
Do 10.06.	Übung 4 (zur Phylogenetik)
Mo 14.06.	Neighbor Joining auf fast additiven Distanzen Übungsblatt 5 (Besprechung am 24.06.)
Do 17.06.	Sichtbarkeit, Fast Neighbor Joining (FNJ)
Mo 21.06.	(Stillarbeit zu technischen Lemmas, FNJ)
Do 24.06.	Übung 5
Mo 28.06.	Genom-Umordnungen, Genomgraph: Adjazenzen und Telomere Umordnungsoperationen auf Genomen, insbesondere DCJ-Operation Genomdistanzen, insbesondere DCJ-Distanz.
Do 01.07.	Berechnung der DCJ-Distanz über Adjazenzgraphen. Übungsblatt 6 (Besprechung am 08.07.)
Mo 05.07.	Einführung in die Massenspektrometrie. Massenzerlegungsproblem.
Do 08.07.	Übung 6 (DCJ, MS)
Mo 12.07.	Selbststudium: Sorting by Block Interchanges. Fragen dazu sind im Skript im entsprechenden Abschnitt. Web server (BiBiServ, Bielefeld) zum Ausprobieren und Hinweise zur Implementierung. Material: Dissertation von D.A. Christie, Kapitel 4.1 bis 4.4 (nur ein paar Seiten)
Do 15.07.	Theoretische Massenspektren. Peptide Mass Fingerprinting.
Mo 19.07.	Einführung in die Ionenmobilitätsspektrometrie. Low-Level-Analyse, Peakmodelle. Peakbestimmung in IMS-Spektren. EM-Algorithmus.
Do 22.07.	Übung 7, Abschluss.