Algorithmische Bioinformatik: Netzwerke, Graphen und Systeme (SS 2016)

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.

Lernziele
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.

Einordnung
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.

Die Modulprüfung besteht, wer mindestens 40% der Punkte zu den Hausaufgaben erreicht und erfolgreich an der Semestralprüfung teilnimmt. Die Semestralprüfung findet als Semestralklausur statt. Die Zusammenarbeit und Abgabe von bis zu 2 Personen ist erlaubt. Dabei ist zu beachten, dass beide in den Übungen in der Lage sein müssen, die gemeinschaftlich erarbeitete Lösung an der Tafel vorzustellen. Wer die Modulprüfung ablegen will, muss sich zur Vorlesung und den Übungen bis zum 22. April anmelden. Die Semestralklausur findet in der letzten Vorlesungswoche statt (typischerweise im letzten Vorlesungsslot im Vorlesungshörsaal). Anmeldung erforderlich.

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

Graphs

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

Complex Networks

• 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

• Review: T. Murata, Petri nets: Properties, Analysis, and Applications, Proceedings of the IEEE, 1989