Algorithmic Bioinformatics: Networks, graphs, and systems (SS 2013)

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.

Learning goals
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.

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

To pass the module exam students obtain at least 40% of the credits in the homework assignments and successfully pass the written exam at the end of the term. Coworking and submission of homework assignments is allowed in groups of two students. The understanding of coworking is that both students in a group can explain the submitted solutions 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).

Based on students preferences, the exam has been postponed by a week and will take place on Wed, Jul 24 in room 105, Amalienstr. 17. Registration for taking the exam is required.

Slides of the lecture and the exercise material can be found here.

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