Algorithmen der Bioinformatik: Signale, Phylogenien und Strukturvorhersagen (WS 12/13)

Die Vorlesung behandelt folgende Themen:

Bestimmung von Signalen

Im Teil I der Vorlesung haben wir uns u.a. damit beschäftigt, wie man die Sequenz von Polynukleotiden bestimmen kann. Hier geht es nun darum, die Bedeutung einer solchen Sequenz herauszuarbeiten. Wir suchen dabei nach interessanten Regionen, so genannte Signale, bei denen es sich beispielsweise um Restriktionsstellen, Bindungsstellen von Proteinen oder auch um Gene oder bestimmte Teile von Genen handeln kann.

Ein dazu oft eingesetzes Paradigma ist das der statistischen Auffälligkeit; es sind jene Regionen einer Sequenz interessant, die sich "außer der Reihe" verhalten. Entsprechend behandelt die Vorlesung den Log-Likelihood Test, die erwartete Häufigkeit (und zugehörige Varianz) eines Wortes in einem zufälligen Text sowie Hidden Markov Modell (HMMs) für die sich vielfältige Anwendungsmöglichkeiten ergeben.

Andere Signale lassen sich durch ein speziellen Musters der zugehörigen Teilwörter charakterisieren. Ein Beispiel hierfür sind sog. Tandem-Repeats (sich zweifach wiederholende Teilwörter), für deren Suche wir einen effizienten Algorithmus entwickeln werden.

Phylogenetische Bäume

Eine wesentliche Aufgabe der biologischen Forschung besteht darin, die Verwandtschaftsbeziehungen innerhalb einer Menge von Objekten (verschiedene Arten, einzelne Gene) zu rekonstruieren. Eine dafür häufig verwendete Methode liegt in der Konstruktion eines sog. phylogenetischen Baums,
der für jedes der Objekte ein Blatt besitzt und dessen inneren Knoten (hypothetische) Vorfahren der Objekte darstellen. In der Vorlesung behandeln wir unterschiedliche Ansätze für die Berechnung solcher Bäume unter der Annahme verschiendester Anforderungen an die Eingaben (ultrametrische Distanzen, additive Bäume, Parsimony).

Strukturvorhersagen

Proteine und RNA-Moleküle sind nur in erster Näherung lineare Moleküle. Durch Wechselwirkungen zwischen den beteiligten Aminosäuren bzw. Nukleotiden falten sie sich in eine dreidimensionale Struktur. Die Struktur ist dabei essentiell für die Funktion des Moleküls. Da Labortechniken zur Bestimmung der 3D-Faltung aufwendig, solche für die Sequezierung jedoch schnell und preisgünstig sind, such man Algorithmen zur Vorhersage der dreidimensionalen Konformation zu einer gegebenen Sequenz. In der Vorlesung behandeln wir sowohl Ansätze der sog. Energieminimierung, als auch stochastische Ansätze, welche auf Grammatik-Modellen (formale Sprachen) der Moleküle basieren.

Die Vorlesung wird im WS 12/13 wird von Sebastian Wild betreut.