392109 Spezielle Algorithmen der Sequenzanalyse (V) (SoSe 2006)

Algorithmische Fragestellungen bei der Analyse endlicher Zeichenketten
werden in der mathematischen und informatischen Literatur schon seit
langer Zeit untersucht. Einen deutlichen Schub hat diese Forschung in
den 1980er und 1990er Jahren durch das Aufkommen der Bioinformatik
erhalten. Dieser Schub begründet sich einerseits qualitativ durch neue
Fragestellungen aus der bioinformatischen Anwendung, andererseits
quantitativ durch die enorme Größe der Datenmengen, mit denen man es im
bioinformatischen Kontext zu tun hat.

In dieser Vorlesung sollen spezielle algorithmische Fragestellungen in
der Sequenzanalyse behandelt werden, die durch die Bioinformatik
aufgeworfen werden. Behandelte Themengebiete sind das paarweise und
multiple Sequenzalignment in verschiedenen Varianten (affine Gapkosten,
linearer Platzbedarf, parametrisches Alignment) sowie der Vergleich
zweier oder mehrerer Genome sowohl auf Sequenz- wie auch auf der
Gen-Ebene.

Teilnahmevoraussetzungen, notwendige Vorkenntnisse

Algorithmen und Datenstrukturen 1+2,
Grundlagen der Sequenzanalyse

Literaturangaben

Durbin, R. et al.: Biological Sequence Analysis, Cambridge University Press,
1998.
Gusfield, D.: Algorithms on Strings, Trees, and Sequences, Cambridge University
Press, 1997.
Setubal, J. & Meidanis, J.: Introduction to Computational Molecular Biology,
PWS Publishing, 1997.