Algorithmische Bioinformatik IIAlgorithmisc Bioinformatics II

Aktuelle HinweiseNews

Die Klausur findet am Donnerstag, 07.02.2019, von 10:00-12:00 Uhr (Schreibzeit) im regulären Vorlesungssaal statt (Amalienstr. 73a, Raum 112). Studierende mit Schreibzeitverlängerung schreiben in der Amalienstr. 17, 4. Stock und beginnen auch um 10:00
Achtung: Die Vorlesung am Do, 25.10. 2018, 10-12, findet wegen der Sitzung des Hochschulrats und der Wahl des Präsidenten der LMU schon morgen, MI, 24.10.2018, 14-16 in der Amalienstr. 17, A105 statt (also anstatt der Übung!)The lecture 25.10.2018, 10-12 will be held tomorrow, Wed, 24.10., 14-16 in hall A105, Amalienstr. 17 (instead of the exercise class)!
Die Nachholklausur Algorithmische Bioinformatik I findet am 17.10.2018 um 14:00-16:00 Uhr in Raum A105 in der Amalienstr. 17 statt. Teilnehmen können alle angemeldeten Teilnehmer, die auch zur 1. Klausur zugelassen waren, und die Prüfung noch nicht erfolgreich abgeschlossen. The second exam Algorithmic Bioinformatics I will take place on Oct 17th 2018 from 14:00-16:00 in room A105, Amalienstr. 17. Participation is possible for all customers which have also been admitted for the first exam but did not pass.

Allgemeine InformationenGeneral Information

Dozent:Lecture

Ralf Zimmer

Umfang und Hörerkreis:Credits and Target audience

4 SWS Vorlesung + 2 SWS Übung / 9 ECTS-Punkte

Vorlesung für Studierende der Bioinformatik im Bereich Bioinformatik

Vorlesung für Studierende der Informatik

Modulniveau: Bachelor

Präsenzstunden: 90 h

Eigenstudium: 180 h

Gesamtaufwand: 270 h

Medienformen: Folienpräsentation, Tafelanschrieb

Lehr- und Lernmethode: Vorlesung, Tutorübung, Aufgaben zum Selbststudium

Turnus: Wintersemester

Zeit und Ort:

Di	10ct-12	Hauptgebäude	M001
Do	10ct-12	Amalienstr. 73a	112

Date and Place:

Tue	10ct-12	LMU main building	M001
Thu	10ct-12	Amalienstr. 73a	112

Übungen:

2 SWS Übung zur Vorlesung

Assistenten:
Markus Joppich
Constantin Ammar
Markus Gruber
Alexander Grün

Bei Fragen zum Übungsbetrieb sind die Assistenten unter der folgenden Vorlesungsmail algo2@bio.ifi.lmu.de erreichbar.

Gruppe 1	Mi	14ct-16	105	Amalienstr. 17
Gruppe 2	Mi	16ct-18	105	Amalienstr. 17

Voraussetzungen und Vorbereitungen

Beherrschung des Stoffs des Bioinformatik bzw. Informatik Grundstudiums der ersten drei Semester.
Es wird empfohlen, bis zum Beginn des Moduls insbesondere den Stoff des Moduls (Grundlagen:) Algorithmen und Datenstrukturen sowie teilweise des Moduls Analysis (zum Thema Differentiation und Integration) aufzufrischen.

Inhalt der VorlesungContent of the lecture

Die Vorlesung gehört zum Grundkanon des Bioinformatikstudiums (4. und 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 zweisemestrigen Zyklus.
Teil I konzentriert sich auf Algorithmenanalyse sowie diskrete und kombinatorische Techniken,
Teil II auf speziellere Methoden der kombinatorischen Optimierung und probabilistische Verfahren.
Der Zyklus kann dann im 6. FS oder Master durch Weiterführende Bioinformatik und unabhängige, weiterführende Spezialvorlesungen der algorithmischen Bioinformatik ergänzt werden: Teil III Netzwerke, Graph und Systeme, Teil IV Algorithmische Systembiologie, Teil V Algorithmen auf Sequenzen, Teil VI: Bäume und Graphen.

Themen der Vorlesung Algorithmische Bioinformatik II sind:

NP-Vollständigkeit: Reduzierbarkeit, NP-vollständige Probleme in der Bioinformatik
Heuristische und approximative Ansätze (PTAS, APX)
Randomisierte Algorithmen
Mehrfaches Sequenzen-Alignment (n-dimensionale DP; heuristische Verfahren; approximative Methoden; Baum-, Consensus-, Profil- und Center-Star-Verfahren; DiAlign; ClustalW)
Probabilistische Modellierung (Orthodoxe und Bayessche Modellierung; Bayessche Inferenz; Optimierung mit constraints; Algorithmen: EM, MC, MCMC, Gibbs Sampling)
Markov-Ketten und Hidden-Markov-Modelle (HMMs) (Modelle; Hauptprobleme; Algorithmen: Forward/Backward, Viterbi, Baum-Welch (EM))
Optional: Clustering Modelle und Algorithmen (CLICK: Graph Partitionierung, probabilistische Graph Modelle)
Optional: Expressiondatenanalyse (Image analysis, Präprozessierung, Normalisierung, Centralization, (Un-/)Supervised Methoden)

Das Modul besteht aus einer Vorlesung sowie Übungen in kleinen Gruppen. Die in der Vorlesung besprochenen Inhalte werden im Übungsteil anhand von praktischen Anwendungen eingeübt. The lecture is part of the basics of the bioinformatics curriculum (4.+5. semester) and deals with algorithmic approaches to bioinformatics Fundamental techniques of algorithm design, of algorithmics, graph theory, mathematical optimization and data analysis as well as probabilistic models and machine learning will be introduced and applied to bioinformatics problems.

The lecture is the second part of a two-semester cycle.
Part I (summer term) focusses on analysis of algporithms as well as on discrte and combinatorial techniques.
Part II (winter term) concentrates on combinatorial optimization and probabilistic approaches, models and inference.
The foundations can be extended in the 6. semester or master courses on Advanced Bioinformatics and specialized topics of algorithmic bioinformatics: Part III Networks, Graphs, and Systems, Part IV Algorithmic Systems Biology, Part V Algorithms on Sequences, Part VI Trees and Graphs. Topics of Algorithmic Bioinformatics II are:

NP-completeness: reductions, NP-complete problems in bioinformatics
heuristic and approximation algorithms (PTAS, APX)
randomized algorithms
multiple alignment (n-dimensional DP; heuristic approaches; approximations; tree, consensus, profile and center star methods; DiAlign; ClustalW)
probabilistic modeling (orthodox and Bayesian modeling; Bayesian inference; optimization with constraints; EM, MC, MCMC, Gibbs sampling)
Markov chains and hidden Markov models (HMMs) (models; main problems; algorithms: forward/backward, Viterbi, Baum-Welch (EM))
Optional: clustering models and algorithms (CLICK: graph partitioning, probabilistic graph model)
Optional: Expression data analysis (image analysis, preprocessing, normalization, centralization, (Un-/)Supervised methods)

Modulprüfung

Beschreibung: Klausur (erfolgreiches Bearbeiten eines Anteils der Hausaufgaben in der Übung ist notwendig zum Bestehen des Moduls).
Prüfungsart: Schriftlich
Prüfungsdauer: 90 min
Hausaufgaben: ja
Eine nicht bestandene Prüfung kann am Semesterende wiederholt werden.

Wer einen Schein erwerben will, muss sich zur Vorlesung und den Übungen bis zum 19.10.2018 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 (bei nicht bestandener Prüfung) findet am ersten Vorlesungstermin Algorithmische Bioinformatik II im vorgesehenen Hörsaal statt.

Hinweise zur Modulprüfung werden in der ersten Vorlesung am 16.10.2018 gegeben.

Material (Slides/Übungsblätter)

Die Folien zur Vorlesung und die Übungsblätter sind hier zu finden

Ein Skript steht zur Verfügung.

Literatur zur Vorlesung

S. Aluru (Ed.): Handbook of Computational Molecular Biology, Chapman and Hall/CRC, 2006.
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.
D. Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
V. Heun: Algorithmische Bioinformatik, Skripten, 2001-2009.
N.C. Jones, P.A. Pevzner: An Introduction to Bioinformatics Algorithms, MIT Press, 2004.
J.C. Setubal, J. Meidanis: Introduction to Computational Molecular Biology, PWS Publishing Company, 1997.
W.-K. Sung: Algorithms in Bioinformatiks: A Practical Introduction, CRC Press, 2010.
M.S. Waterman: Introduction to Computational Biology: Maps, Sequences, and Genomes, Chapman and Hall, 1995.