Algorithmische Bioinformatik: Systeme und Netzwerke (SS 2008)

Die Vorlesung gehört zum Grundkanon des Bioinformatikstudiums (6. Fachsemester) und behandelt grundlegende algorithmische Ansätze der Bioinformatik. Die Vorlesung rundet die beiden einführenden Veranstaltungen Algorithmische Bioinformatik I und II ab und vertieft sowohl diskrete als auch probabilistische Modelle und zugehörige Algorithmen anhand von aktuellen Bioinformatikproblemen. Grundlegende Techniken des Algorithmenentwurfs, der Algorithmik, der Graphentheorie, der mathematischer 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 diskrete und kombinatorische Techniken, Teil II auf probabilistische Verfahren, Teil III auf speziellere Methoden der kombinatorischen Optimierung und Graphalgorithmen sowie aktuelle Bioinformatikprobleme. Themenbereiche sind im SS 2008 insbesondere "Graphen, Netze und Netzwerke". Dabei wird eine Einführung in Graphtheorie und -algorithmen, Petrinetze und Bayes'sche Netzwerke gegeben. Spezielle Netzwerke und Netzwerkeigenschaften (scale-free nets, network modules) werden anhand molekularer (metabolische und regulatorische) Netzwerke diskutiert. Anwendungen in der Bioinformatik reichen von Netzwerk-Datenbanken und -Libraries über Techniken zur Netzwerk-Modellierung und -Inferenz, bis hin zu speziellen Bioinformatik- Analyseverfahren und Tools zur Visualisierung und Simulation biomolekularer Netzwerke.

Graphs

• Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983
• Martin C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, 1980
• Shimon Even, Graph Algorithms, Computer Science Press, 1979
• Denes König, Theorie der endlichen und unendlichen Graphen, (1935) Chelsea Publ., 1950
• Frank Harary, Graph Theory, Addison-Wesley, 1969
• Dieter Jungnickel, Graphs, Networks and Algorithms, (1998) Springer, 2005


• Cormen, Leiserson, Rivest(, Stein), Introduction to Algorithms, (1990) MIT Press, 2001

Complex Networks

• Duncan Watts, Small Worlds, Princeton University Press, 1999
• Albert-Laszlo Barabasi, Linked, Plume Books, 2003
• Mark Buchanan, Nexus, Norton, 2002
• Steven H. Strogatz, Nonlinear Dynamics and Chaos, 2001
• Steven H. Strogatz, Sync, Theia, 2004
• Duncan Watts, Six Degrees, Norton, 2004
• Bornholdt&Schuster, Handbook of Graphs and Networks, Wiley, 2004


• Review: R.Albert & A.-L.Barabasi, Statistical mechanics of complex networks, Reviews of modern physics, Vol 74, Jan. 2002

Random Graphs

• Bela Bollobas, Random Graphs, Cambridge University Press, 2001

Petri Nets

• Bernd Baumgarten, Petri-Netze, Spektrum, 1996
• Priese&Wimmel, Petri-Netze, Springer, 2002
• Jörg Desel, Petrinetze, lineare Algebra, und lineare Programmierung, Teubner, 1998
• Wolfgang Reisig, Petri-Netze, Eine Einführung, Springer, 1985
• Wolfgang Reisig, Petri-Netze, Systementwurf mit Netzen, Springer, 1985


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

Bayesian Networks

• Finn V. Jensen, Bayesian Nwtworks and Decision Graphs, 1996
• Judea Pearl, Probabilistic Reasoning in Intelleigent Systems, Morgan Kaufman, 1988
• Neapolitan, Learning Bayesian Networks, Prentice Hall, 2003
• (Tom Mitchell, Machine Learning, Mac Graw Hill, 1997)
• (Hastie, Tibshirani, Friedman, The Elements of Statistical Learning, Springer, 2001)


• Review: D. Heckerman, A tutorial on Learning with Bayesian Networks, Microsoft Research TR, 1996