AG Algorithmen und Komplexität

Computational Biology: Alignments and Sequencing (SS 15)

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 dealing with strings. This includes

  • computing similarities of strings,
    (suffix trees and their applications)
  • finding approximate matches and
    (pairwise and multiple alignments)
  • reconstructing texts from overlapping fragments.
    (partial digest and double digest methods, PQ-trees, shortest common superstrings)

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, that is from Apr 21st to Jul 21st. Individual sessions will take place weekly on

  • Lecture: Tuesdays, 10:00 - 11:30 in 48-654
  • Exercise Class (bi-weekly): Tuesdays, 13:45 - 15:15 in 48-654, starting on May 12th.

Note: There will be no lecture on June 9th and July 21st (new!). The exercise on July 21st has been moved to July 22nd, 15:30 in the usual room (new!).


Exercises are organized by Robert.

There will be exercise sheets with problems relating to the current lecture material.


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

Computational Biology I (WS 13/14)