Grundlagen der Sequenzanalyse

Dr. Sven Rahmann, Dipl.-Bioinf. Katharina Jahn

Vorlesung 392011 und Übungen 392012 im Wintersemester 2006/2007
Donnerstag 8:30 bis 10:00 Uhr in H3

Aktuelles

Die Ergebnisse der Klausur vom 08.02.2007 stehen hier zum Download bereit und hängen auch vor U10-146 aus.

Wichtig für die Nachklausur: Bitte vor dem 1.3. in die Liste vor U10-146 eintragen, ggf. unmögliche Termine angeben. Geplant ist ein Termin Ende März. Aus rechtlichen Gründen muss die Nachklausur noch im Wintersemester stattfinden.

Kurzbeschreibung

Sequenzen sind allgegenwärtig. Texte und Programme, Gene und Proteine, Polygonzüge, Sprach- und Bildsignale und digitalisiertes Vogelzwitschern 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 algorithmische Komplexität von entscheidender praktischer Bedeutung ist.
In der Vorlesung werden Algorithmen zum effizienten Vergleich von Sequenzen und zur Suche exakter und approximativer Muster in Sequenzen behandelt. Viele dieser Algorithmen sind durch bioinformatische Fragestellungen motiviert. Sie finden jedoch auch Anwendungen in anderen Bereichen wie z.B. der Textverarbeitung und der Datenkompression.

Voraussetzungen

Literatur

Altes(!) Skript zur Vorlesung. Ein neues 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 ersten Vorlesung am 19.10. Nach- und Ummeldungen bitte an Katharina Jahn .

Do 14-16 Uhr in U2-119. Tutorin: Katharina Jahn
Do 18-20 Uhr in V2-121. Tutorin: Schokoufeh Ghezelbash
Fr 08-10 Uhr in E01-108. Tutor: Sven Twardziok

Zeitplan

Datum	Vorlesung	Übungsblatt	Abgabe
19.10.2006	Organisatorisches; Metriken auf Sequenzen	Blatt 1	26.10.2006
26.10.2006	Edit-Operationen, Edit-Distanz und verwandte Distanzen	Blatt 2	02.11.2006
02.11.2006	Maximal matches Distanz	Blatt 3	09.11.2006
09.11.2006	q-gram Distanz	Blatt 4	16.11.2006
16.11.2006	Äquivalenz von Distanzen und Ähnlichkeiten	Blatt 5	23.11.2006
23.11.2006	Paarweises Sequenzalignment (global, lokal, Varianten)	Blatt 6	30.11.2006
30.11.2006	Affine Gapkosten, suboptimale Alignments, Sellers' Algorithmus	Blatt 7	07.12.2006
07.12.2006	Dotplots, BLAST, FASTA	Blatt 8 GPCRs.fasta	14.12.2006
14.12.2006	FASTA, SWIFT, q-gram Index	Blatt 9	21.12.2006
21.12.2006	Statistik von Matches und lokalen Alignments Suffixbäume	Blatt 10	11.01.2007
11.01.2007	Suffixbäume und Suffix-Arrays	Blatt 11	18.01.2007
18.01.2007	Konstruktion von Suffixbäumen und Suffix-Arrays	Blatt 12	25.01.2007
25.01.2007		Blatt 13	01.02.2007
01.02.2007	PSSMs, Sequenzlogos. Wiederholung	---	---
08.02.2007	Klausur um 8:15 in H3. Beginn: 8:30 Uhr.	---	---

Scheinkriterien und Informationen zur Klausur

Die Klausur zu dieser Veranstaltung findet am 8. Februar 2007 zwischen 8:30 und 10:00 in Hörsaal 3 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 3. 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.
Weitere Voraussetzung für die Teilnahme an der Klausur sind die regelmäßige Teilnahme an den Übungen, zweimaliges Vorrechnen, und mindestens 60 Prozent der erreichbaren Punkte bei den Übungsaufgaben.

Genome Informatics