Spezielle Algorithmen der Sequenzanalyse (Sequenzanalyse II)

Dr. Sven Rahmann, Dipl.-Inf. Peter Husemann, Dipl.-Biol. Constantin Bannert

Vorlesung 392010 und Übungen 392011 im Sommersemester 2007
Freitags 8:30 bis 10:00 Uhr in H14

---

Kurzbeschreibung

Wir werden einerseits Themen, die aus der Grundvorlesung bekannt sind, vertiefen, z.B. effiziente Implementierungen von Suffixbäumen und Suffixarrays, Alignment mit linearem Platzbedarf (Hirshberg-Technik), wie hängt das optimale Alignment von der benutzten Scorefunktion ab (parametrisches Alignment), längennormalisiertes Alignment

Weiterhin betrachten wir neue Probleme und Modelle, z.B. RNA-Sekundärstrukturvorhersage (Nussinov-Algorithmus), Transkriptionsfaktorbindestellenvorhersage mit Hilfe von position weight matrices (PWMs), sowie die Modellierung von genomischen Signalen (wie CpG islands oder Genstrukturen) mit Hidden Markov Modellen (HMMs).

Wir werden uns auch vermehrt anwendungsorientierten Algorithmen zuwenden: Vergleich ganzer Genome, Finden von repeats, etc.

Voraussetzungen

• Algorithmen und Datenstrukturen I+II
• Sie können an der Prüfung teilnehmen, auch wenn Sie die Klausur von Sequenzanalyse I nicht bestanden haben. Der Stoff wird jedoch vorausgesetzt.
• ekvv-Registrierung Vorlesung
• ekvv-Registrierung Übung

Literatur

• Ein {{:teaching:2007summer:sequenzanalyse:skriptsequenzanalyse.pdf | Skript }} ist hier im Aufbau.
• Prof. Volker Heun an der TU München hat auch eine gute Skriptsammlung .
• Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York, 1997.
  
• Setubal, J. and Meidanis, J.: Introduction to Computational Biology. PWS Publishing, Boston, M.A., 1997.

Übungen

Einteilung in der zweiten Semesterwoche per e-mail. Nach- und Ummeldungen bitte an Peter Husemann .

• Di 14-16 Uhr in V4-106. Tutor: Sven Twardziok
• Mi 10-12 Uhr in M3-115. Tutorin: Sandra Kästner
• Mi 12-14 Uhr in T2-233. Tutor: Peter Husemann

Zeitplan

Datum	Vorlesung	Übungsblatt	Abgabe
06.04.2007	[Karfreitag]	---	---
13.04.2007	Organisatorisches; WOTD-Suffixbaum-Konstruktion	{{:teaching:2007summer:sequenzanalyse:blatt00.pdf | Blatt 0 }} (Wiederholung)	20.04.2007
20.04.2007	Manber-Myers-Suffixarray-Konstruktion	{{:teaching:2007summer:sequenzanalyse:blatt01.pdf | Blatt 1 }}	27.04.2007
27.04.2007	RNA-Sekundärstruktur-Vorhersage: Nussinov	{{:teaching:2007summer:sequenzanalyse:blatt02.pdf | Blatt 2 }}	04.05.2007
04.05.2007	Special lecture: PASSTA	{{:teaching:2007summer:sequenzanalyse:blatt03.pdf | Blatt 3 }}	11.05.2007
11.05.2007	Paarweises Alignment mit linearem Platzbedarf	{{:teaching:2007summer:sequenzanalyse:blatt04.pdf | Blatt 4 }}	18.05.2007
18.05.2007	Längennormalisiertes und Parametrisches paarweises Alignment	{{:teaching:2007summer:sequenzanalyse:blatt05.pdf | Blatt 5 }} {{:teaching:2007summer:sequenzanalyse:parametricalignment.ppt | [.ppt] }} zu parametrischem Alignment	25.05.2007
25.05.2007	Multiples Alignment: Definitionen, Probleme	{{:teaching:2007summer:sequenzanalyse:blatt06.pdf | Blatt 6 }}	01.06.2007
01.06.2007	Sum-of-pairs, Carillo-Lipman	{{:teaching:2007summer:sequenzanalyse:blatt07.pdf | Blatt 7 }}	08.06.2007
08.06.2007	Center-star, Divide-and-conquer Alignment	{{:teaching:2007summer:sequenzanalyse:blatt08.pdf | Blatt 8 }}	15.06.2007
15.06.2007	Tree-Alignment	{{:teaching:2007summer:sequenzanalyse:blatt09.pdf | Blatt 9 }}	22.06.2007
22.06.2007	progessives Alignment	{{:teaching:2007summer:sequenzanalyse:blatt10.pdf | Blatt 10 }}	29.06.2007
29.06.2007	Genomvergleich	{{:teaching:2007summer:sequenzanalyse:blatt11.pdf | Blatt 11 }}	06.07.2007
06.07.2007	Wiederholung	---	---
13.07.2007	Klausur um 8:15 in H14. Beginn: 8:30 Uhr.	---	---

Scheinkriterien und Informationen zur Klausur

• Die Klausur zu dieser Veranstaltung findet am 13. Juli 2007 zwischen 8:30 und 10:00 in Hörsaal 14 statt. Es wird um frühzeitiges Erscheinen bis 8:15 Uhr gebeten.
• Grundlage für die Klausur ist das Skript zur Vorlesung. Auch in der Vorlesung übersprungene, aber in den Übungen behandelte Abschnitte sind prüfungsrelevant.
• Für Studierende im 4. Semester BiG-Bachelor ist der erfolgreiche Abschluss des Moduls Algorithmen und Datenstrukturen Voraussetzung für die Teilnahme an der Klausur. Dies wird in der Woche vor der Klausur für alle im eKVV eingetragenen Teilnehmer überprüft. Deshalb ist es notwendig, sich für die Teilnahme an der Klausur dort zu registrieren.
• Die Übungen sind freiwillig, der Besuch wird jedoch dringend empfohlen!