Algorithmische Bioinformatik: Netzwerke, Graphen und SystemeAlgorithmic Bioinformatics: Networks, Graphs, and Systems

Inhalte der Vorlesung "Algorithmische Bioinformatik: Netzwerke, Graphen und Systeme": Theorie komplexer Netzwerke; Eigenschaften biologischer Netzwerke (scale-free nets, network modules); Graphtheorie und Graphalgorithmen, Spezifikation von Systemen mit Petrinetzen.
Das Modul kann in Deutsch oder Englisch durchgeführt werden, abhängig von den Wünschen der Teilnehmer. Content of the lecture "Algorithmic Bioinformatics: Networks, graphs, and systems": Theory of complex networks; Properties of biological networks (scale free networks, network modules); Graph theory and graph algorithms, Specification of systems with Petri nets.
The module will be given in German or English, depending on students choice.

Aktuelle HinweiseNews

Die Klausur findet am 19.02. 12:00 s.t. in Raum A105 in der Amalienstr. 17 statt.
Die erste Vorlesung findet am 24. Oktober 2017, 10 Uhr statt.
The first lecture starts at 10h, Oct 24, 2017.
Für die Teilnahme zur Vorlesung ist eine Anmeldung bis zum 24. Oktober 2017 notwendig. Bitte melden Sie sich bis Ende dier Woche (Fr, 20.10.2017) an, um sicherzustellen, dass die Veranstaltung stattfindet.
A registration until Oct 24 is required for the lecture. Please register until the end of the week (Fri, Oct. 20, 2017) to ensure that the course will take place !

Allgemeine InformationenGeneral Information

Dozent:Lecturer:

Ralf Zimmer

Übungsleiter:Class:

Evi Berchtold

Alexander Grün

Umfang:Credits

SWS 4V+2Ü (9 ECTS)

Zeit und Ort:Time and Place

DiTue	10-12	Amalienstr. 17, A406
DoThu	10-12	Amalienstr. 17, A406

Klausur:Exam:

Übungen:Exercises

2 SWS Übung zur VorlesungExercise class
Assistent: Evi Berchtold

Di/Tue

10:00 s.t.-12

Amalienstr. 17, A105

Inhalt der VorlesungContent of the lecture

Inhalte der Vorlesung Algorithmische Bioinformatik: Netzwerke, Graphen und Systeme sind unter anderem: Einführung in Graphtheorie und -algorithmen, komplexe Netzwerke und Netzwerkeigenschaften (scale-free nets, network modules), Petrinetze, Bayes'sche und Boolsche Netzwerke. Content of the lecture Algorithmic Bioinformatics: Networks, graphs, and systems contains: Introduction to graph theory and graph algorithms, complex networks and network properties (scale free networks, network modules), Petri nets, Bayes networks, Boolean networks.

LernzieleLearning goals
Hörer der Vorlesung sollen einen guten Überblick über Algorithmen, Verfahren und Anwendungen von Grahen und Netzwerken in der Bioinformatik bekommen und diese auch konkret umsetzen und für neue Fragestellungen anpassen können. Insbesondere verstehen die Studenten den Unterschied zwischen einfachen Graphen/Netzwerken und Systemen (Graphen mit Semantik) in der Bioinformatik. Hörer sollen auch hier Konzepte praktisch umsetzen, anwenden und anpassen können. Participants should get a good overview of algorithms, approaches, and applications of graphs and networks in bioinformatics. Students can implement them and apply them to actual reserach quetsions. In particular students should understand the difference between simple graphs/networks and systems (graphs with a semantic) in bioinformatics. Again students will be able to practically implement, apply, and adapt these concepts.

EinordnungBackground
Die Vorlesung gehört zum Grundkanon des Bioinformatikstudiums (ab 6. 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 dritte 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. The lecture is part of the basic lecture series of the bioinformatics programme (semester 6 and above) and trets algorithmic aspects of bioinformatics. Fundamental techniques of algorithm design, 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 third part of a three semester cycle. Part I focusses on analysis of algorithms and discrete and combinatorial techniques, Part II on special methods of combinatorial optimization and approximation as well as on probabilistic models and algorithms. Part II on graph algorithms and and network and systems theory.

ModulprüfungModule exam

Die Modulprüfung besteht, wer mindestens 50% der Punkte zu den Hausaufgaben erreicht und erfolgreich an der Semestralprüfung teilnimmt. Die Semestralprüfung findet als Semestralklausur statt. Die Aufgaben müssen alleine bearbeitet werden und jeder muss in der Lage sein, seine erarbeitete Lösung an der Tafel vorzustellen. Wer die Modulprüfung ablegen will, muss sich zur Vorlesung und den Übungen anmelden (siehe oben). Die Semestralklausur findet in der letzten Vorlesungswoche statt (typischerweise im letzten Vorlesungsslot im Vorlesungshörsaal). Anmeldung erforderlich. To pass the module exam students obtain at least 50% of the credits in the homework assignments and successfully pass the written exam at the end of the term. Exercises have to be solved individually and each student has to be able to explain his or her solution in the exercise class. In order to participate in the exam, a registration for the lecture and the exercise is required (see above). The written exam will take place in the last week of the lecturing term (typically during the last lecture slot in the lecture hall).

Material/Folien/übungMaterial/slides/exercise

Die Folien zur Vorlesung und die Übungsblätter sind hier zu finden. Slides of the lecture and the exercise material can be found here.

Literatur zur VorlesungLiterature for the lecture

Graphs

Text book: Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press, 2001 (3rd. ed. 2009)
Text book: Claude Berge, Graphs and hypergraphs, Amsterdam, North-Holland Publ., 1973
Text book: Korte & Vygen, Combinatorial Optimization. Theory and Algorithms (Algorithms and Combinatorics) , Springer Verlag, 2000
Text book: Dieter Jungnickel, Graphs, Networks and Algorithms, (1998) Springer, 2005

Complex Networks

Text book: Barabasi, A.L., Network Science, Cambridge University Press, 2016, 456 pp.
Review: R.Albert & A.-L.Barabasi, Statistical mechanics of complex networks, Reviews of modern physics, Vol 74, Jan. 2002
Review: Newman, M., The structure and function of complex networks, SIAM Review, 2003, 45, 167- 256
Review: Dorogovtsev, S. & Mendes, J., Evolution of networks , Adv. Phys, 2002, 51, 1079-1187
Fox Keller, E., Revisiting "scale-free" networks, Bioessays, 2005, 27, 1060-1068

Petri Nets

Text book: I. Koch, W. Reisig, F. Schreiber (Eds.), Modeling in Systems Biology - The Petri Net Approach , Springer, 2011
Text book: K. Jensen, L.M. Kristensen, Coloured Petri Nets , Springer, 2009
Review: T. Murata, Petri nets: Properties, Analysis, and Applications, Proceedings of the IEEE, 1989