AG Algorithmen und Komplexität

Computational Biology: Alignments and Sequencing (WS 13/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 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 Oct 21st to Feb 8th. Individual sessions will take place weekly on

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


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