Algorithmische Bioinformatik II (WS 2011/12)

Beherrschung des Stoffs des Bioinformatik bzw. Informatik Grundstudiums.

Die Vorlesung gehört zum Grundkanon des Bioinformatikstudiums (5. Fachsemester) und behandelt algorithmische Ansätze der Bioinformatik. Grundlegende Techniken des Algorithmenentwurfs, der Algorithmik, der Graphentheorie, der mathematischen Optimierung und Datenanalyse, sowie probabilistische Modelle und maschinelles Lernen werden eingeführt und auf Bioinformatikprobleme angewendet. Die Vorlesung ist der zweite Teil eines dreisemestrigen Zyklus. Teil I konzentriert sich auf Algorithmenanalyse sowie diskrete und kombinatorische Techniken, Teil II auf speziellere Methoden der kombinatorischen Optimierung und probabilistische Verfahren, und Teil III auf Netzwerk-Theorie und Graphalgorithmen.

Inhalte der Vorlesung Algorithmische Bioinformatik II sind unter anderem: Approximative Alignments, FASTA und BLAST, Multiple Testing Korrekturen, Scorig Matrizen Multiple-, Progressive- und Profil-Alignments. Kombinatorische Optimierung, Maximum Likelihood Schätzung, EM Algorithmus, Zufallszahlengenerierung, Monte Carlo Methoden, Markov Ketten, Random Walks, Hidden Markov Modelle.

Wer einen Schein erwerben will, muss sich zu den Übungen bis zum 30. Oktober anmelden.

Einen Schein erhält, wer erfolgreich an der Semestralprüfung (Klausur) teilnimmt. Die Note des Scheins ergibt sich aus der Bewertung der Klausur.

Die Semestralprüfung findet als schriftliche Prüfung statt. Voraussetzung für die Zulassung zur Klausur sind die regelmäßige Teilnahme an den Übungen und das Erreichen von 50% der Punkte aus den Übungsaufgaben.

Die Semestralklausur findet am letzten Vorlesungstermin des Semesters im Hörsaal statt

Die Wiederholungsklausur findet am ersten Vorlesungstermin Algorithmische Bioinformatik: Systeme und Netzwerke im vorgesehenen Hörsaal statt.

Vorgaben für die Abgabe der Übungsaufgaben

Übungsblatt	Abgabe am	Dateien	Lösungen
Blatt 1	31.10.2011	Dateien Aufgabe 3
Blatt 2	08.11.2011	Aho-Corasick aus AlgBio 1 Aho-Corasick Publikation Dateien Aufgabe 2 Dateien Aufgabe 3
Blatt 3	15.11.2011	Dateien Aufgabe 3 Dateien Aufgabe 4
Blatt 4	22.11.2011	Altschul-Gish Publikation Dateien Aufgabe 4
Blatt 5	29.11.2011	Dateien Aufgabe 4
Blatt 6	06.12.2011	Datei Aufgabe 1 Dateien Aufgabe 4
Blatt 7	13.12.2011	Datei Aufgabe 1 Aktualisiert 07.12. 12:30 Dateien Aufgabe 3
Blatt 8	13.12.2011	Datei Aufgabe 2 Durbin et al.
Blatt 9	10.01.2012
Blatt 10	17.01.2012
Blatt 11	24.01.2012
Blatt 12	31.01.2012	Datei Aufgabe 2
Blatt 13 (BONUS)	07.02.2012	Die Aufgaben sind klausurrelevant!

Folien zur Vorlesung sind hier zu finden.

• S. Aluru (Ed.): Handbook of Computational Molecular Biology, Chapman and Hall/CRC, 2006.
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Potasi: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability, Springer, 1999.
• H.-J. Böckenhauer, D. Bongartz: Algorithmische Grundlagen der Bioinformatik: Modelle, Methoden und Komplexität, Teubner, 2003.
• P. Clote, R. Backofen: Computational Molecular Biology - An Introduction, Wiley, 2000.
• R.C. Deonier, S. Tavare, M.S. Waterman: Computational Genome Analysis, Springer, 2005.
• R. Durbin, S. Eddy, A. Krogh, G. Mitchinson: Biological Sequence Analysis - Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press, 1998.
• W.J. Ewens, G.R. Grant: Statistical Methods in Bioinformatics, Springer, 2001.
• D. Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
• V. Heun: Algorithmische Bioinformatik, Skriptum, 2001-2011.
• A. Isaev: Introduction to Mathematical Methods in Bioinformatics, Springer, 2004.
• N.C. Jones, P.A. Pevzner: An Introduction to Bioinformatics Algorithms, MIT Press, 2004.
• T. Koski: Hidden Markov Models for Bioinformatics, Kluwer Acedimics Publishers, 2001.
• D.W. Mount: Bioinformatics - Sequence and Genome Analysis, Cold Spring Harbor Laboratory Press, 2001.
• J.C. Setubal, J. Meidanis: Introduction to Computational Molecular Biology, PWS Publishing Company, 1997.
• M.S. Waterman: Introduction to Computational Biology: Maps, Sequences, and Genomes, Chapman and Hall, 1995.
• I. Wegener: Komplexitätstheorie - Grenzen der Effizienz von Algorithmen, Springer 2003.