Sequenzen sind allgegenwärtig. Texte und Programme, Gene und Proteine, Sprach- und Bildsignale werden dargestellt als Zeichenfolgen über einem endlichen Alphabet. Entsprechend vielfältig sind die algorithmischen Fragestellungen. Oft ist dabei der Datenumfang sehr groß, so dass die Komplexität der zur Problemlösung verwendeten Algorithmen von entscheidender praktischer Bedeutung ist. In der Vorlesung werden effiziente Algorithmen zur Suche und Analyse, sowie zum Vergleich von Sequenzen behandelt. Viele dieser Algorithmen sind durch biologische Fragestellungen motiviert. Sie finden jedoch auch Anwendungen in anderen Bereichen wie z.B. bei der Suche in großen Sammlungen von XML-Dokumenten.

Die Vorlesung ist neu konzipiert und enthält vielfältige Querbezüge zur Datenkompression. So beruhen z.B. neuartige Index-Datenstrukturen auf der Burrows-Wheeler Transformation, die auch bei neueren Datenkompressionverfahren eine entscheidende Rolle spielt.

Script

Übungsblatt 1

Hinweis: In Kalenderwoche 21 findet sowohl am Dienstag (Übungsblatt 2) als auch am Donnerstag (Übungsblatt 3) eine Übung statt.

Übungsblatt 2
Testdaten zum Übungsblatt 2.

Übungsblatt 3

Übungsblatt 4
Testdaten zum Übungsblatt 4.

Übungsblatt 5

Übungsblatt 6

• D. Gusfield: Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.