Modul 39-Inf-ASB Algorithmische Stochastik in der (Bio-)Informatik

Der Schwerpunkt der Vorlesung liegt auf der Vermittlung von verschiedenen Methoden und Techniken als "Werkzeuge" für ein breites Spektrum von Problemen aus der (Bio-)Informatik. Die Studierenden lernen, in Wahrscheinlichkeiten zu denken und mit Wahrscheinlichkeitsverteilungen und ihren numerischen Eigenschaften umzugehen. Als Vorbereitung auf die Abschluss-Arbeit wird insbesondere in den Übungen verlangt, besprochene Methoden auf neue Probleme zu übertragen. Die Übungen beinhalten deswegen auch Programmier- und Projektaufgaben, in denen die Verfahren aus der Vorlesung implementiert und angewendet werden. Eine Vielzahl von Anwendungen aus der aktueller Forschungsliteratur wird von den Studierenden im Seminar erarbeitet und vorgetragen.

The lecture course focusses on the various methods and techniques as `tools' for a wide spectrum of problems from bioinformatics and informatics in the sciences. The students learn to think in terms of probabilities and to deal with probability distributions and their numerical properties. In the assignments, they will be asked to apply the methods to new problems. The assignments also contain programming exercises, in which the methods presented in the lecture are to be implemented and applied. In the seminar, students deal with the interface to the current research literature.

Viele komplexe Probleme der Bio- und allgemeiner der naturwissenschaftlichen Informatik (z.B. Alignment, Gene finding, Inferenz fuer Populationssequenzdaten) lassen sich nicht gleichzeitig effizient und optimal mit deterministischen Verfahren lösen; in diesem Fall nimmt man oft stochastische Methoden zur Hilfe. Aufbauend auf stochastischen Grundlagen aus der Wahrscheinlichkeitstheorie und Statistik legt dieses Modul die nötigen Grundlagen (Darstellung von Verteilungen im Computer; Rechnen mit sehr kleinen Wahrscheinlichkeiten; Effiziente Generierung von Zufallszahlen aus vorgegebenen Verteilungen; Testen der Qualität von Zufallszahlengeneratoren). Als ein wichtiges Hilfsmittel werden Markov Chain Monte Carlo Methoden (Metropolis-Hastings; Gibbs sampler) anhand von Anwendungsbeispielen vorgestellt, sowie Methoden des importance sampling und der Simulation seltener Ereignisse.

Literatur:

• James E. Gentle. Random Number Generation and Monte Carlo Methods. Springer 1998.
• Christian P. Robert und George Casella. Monte Carlo Statistical Methods. Springer 2002.
• Donald E. Knuth. The Art of Computer Programming vol. 2. Addison-Wesley 1998.
• Neil Madras, Lectures on Monte Carlo Methods, AMS 2002.
• James Bucklew, Introduction to Rare Event Simulation, Springer 2004.

Many complex problems in bioinformatics and informatics in the sciences (like alignment, gene finding, inference from population sequence data) cannot be solved efficiently with deterministic algorithms; instead, one often resorts to stochastic methods. Starting from the basics of probability theory and statistics, this module lays the foundations of algorithmic stochastics (representation of distributions in the computer; computing with very small probabilities; random number generation; generation of random numbers from various distributions; testing the quality of random number generators). Furthermore, Markov chain Monte Carlo methods (Metropolis-Hastings; Gibbs sampler) will be presented, as well as methods of importance sampling and rare event
simulation.

Literature:

• James E. Gentle. Random Number Generation and Monte Carlo Methods. Springer 1998.
• Christian P. Robert and George Casella. Monte Carlo Statistical Methods. Springer 2002.
• Donald E. Knuth. The Art of Computer Programming vol. 2. Addison-Wesley 1998.
• Neil Madras, Lectures on Monte Carlo Methods, AMS 2002.
• James Bucklew, Introduction to Rare Event Simulation,

Springer 2004.

Mathematik für Informatik I und II,
24-M-VTB oder 24-M-VTN

Knowledge as in the modules 24-M-INF1 Mathematik für Informatik I, 24-M-INF2 Mathematik für Informatik II, 24-M-VTB Vertiefung Mathematik für die Bioinformatik or 24-M-VTN Vertiefung Mathematik für die Naturwissenschaften

—