Lehrende: Prof. Dr. Stefan Kurtz
Veranstaltungsart: Vorlesung
Anzeige im Stundenplan: GSA VL
Semesterwochenstunden: 2
Unterrichtssprache: Deutsch
Min. | Max. Teilnehmerzahl: - | 30
Kommentare/ Inhalte: Motiviert durch den biologischen Anwendungskontext werden grundlegende Modelle und Methoden für die Speicherung, den Vergleich und die Analyse von biologischen Sequenzen behandelt. Die betrachteten Methoden werden hinsichtlich ihrer Adäquatheit für die Problemstellungen sowie hinsichtlich ihrer Effizienz untersucht. Neben den algorithmischen Aspekten der Probleme werden auch statistische Fragestellungen betrachtet, z.B. hinsichtlich der Signifikanz des Ergebnisses eines Ähnlichkeitsvergleichs. In den Übungsaufgaben werden einfache Beweise zu Eigenschaften der betrachteten Algorithmen geführt, sowie deren Implementierungsaspekte diskutiert. Die Vorlesung gliedert sich in die folgenden Themen: * Das Modell der Edit Distanz * Lokale Ähnlichkeit * Approximative Suche * Überlappungen bei der Fragment-Assemblierung * Lineare und Affine Gapkosten * Das Maximal Matches Distanz Modell * Das q-wort Distanz Modell * Methoden zur Datenbanksuche
Lernziel: Die Studierenden beherrschen die grundlegenden Modelle und Algorithmen der Sequenzanalyse und können diese für verwandte Fragestellungen modifizieren. Sie sind in der Lage die Algorithmen unter verschiedenen Gesichtspunkten wie z.B. Effizienz und Genauigkeit zu beurteilen und auf Standardfragestellungen anzuwenden. Die Studierenden erkennen grundlegende Beschränkungen der Algorithmen. Die Studierenden beherrschen verschiedene grundlegende Techniken zur Implementierung der Algorithmen und können Software entwickeln, um z.B. das optimale Alignment zweier Sequenzen zu berechnen.
Vorgehen: Vorlesung mit Einsatz der Tafel und Folienpräsentation
Literatur: Stefan Kurtz. Vorlesungsskript Grundlagen der Sequenzanalyse; J. Setubal and J. Meidanis. Introduction to Computational Molecular Biology. PWS Publishing, Boston, M.A., 1997. D. Gusfield. Algorithms on Strings, Trees, and Sequences, Cambridge University Press, New York, 1997.