Algorithmen zur Sequenzanalyse

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

• E. Ohlebusch: Bioinformatics Algorithms, Oldenbusch Verlag, 2013.
• D. Gusfield: Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.