AG Algorithmen und Komplexität

Computational Biology: Signals, Phylogenetics and Structure Prediction (SS 14)

Biologists collect ever more data which we can only hope to evaluate using computers. In particular, there are huge databases of DNA and RNA resp. fragments thereof, which we model as strings. The sheer amount of data and size of individual records demands especially efficient algorithms if we want to obtain results in a timely fashion.

This course contains computer science methods for advanced, biologically motivated analysis of string-based data, in particular

  • identifying signals, patterns in strings of statistical significance,
    (log-likelihood test, hidden markov models)
  • reconstructing phylogenetic trees and
    (hierarchical clustering, tree metrics, perfect phylogenetics, quartett puzzling)
  • predicting folding structure of RNA.
    (minimum free energy secondary structures, stochastic context-free grammars)

We always bear in mind to keep complexities low.

It is a 4 ECTS entry-level master course with accompanying tutorials; find details in the official documents.


In order to participate in the exercise classes, you are required to register in the OLAT system.


Lectures and exercise sessions will be held throughout the reading period. Individual sessions will take place weekly on

  • Lecture: Tuesdays, 10:00 - 11:30 in 48-654
  • Exercise Class (biweekly): Fridays, 13:45 - 15:15 in 48-654
    first exercise class on 09.05.2014


Exercises are organized by Sebastian.

Lecture Notes

Here you can download the content of the electronic blackboard from class as pdf.


There will be oral exams at the end of the semester, please contact us in time to make an appointment. You need at least 40% of the achievable points in the exercises to be allowed to take the exam.

Suggested Reading

German lecture notes covering all course material are available in print; ask us for it!

Apart from the lecture notes, the following text books cover most of the course's content:

  • R. Durbin, S. Eddy, A. Krogh, G. Mitchison: Biological Sequence Analysis
    Cambridge University Press, 1998
  • D. Gusfield: Algorithms on Strings, Trees, and Sequences
    Cambridge University Press, 1997

Previous Iterations

WS 12/13