Table of Contents
Algorithmen auf Sequenzen
Diese Veranstaltung findet im Wintersemester 2012/2013 statt. Orientieren Sie sich auch an der Veranstaltungsseite zu Algorithmen auf Sequenzen aus dem Sommersemester 2011.
Skript
Aktueller Skript-Entwurf – zuletzt aktualisiert am 24.01.2013
Termine
Vorlesung: Mi 8-10 in MSW16 E32 (erste Vorlesung: 10.10.2012)
Übung: Do 8:15-9:00 und 9:00-9:45 in OH14 R304 (erste Übung: 18.10.2012)
Kontakt
Veranstalter: M. Martin
Die Veranstaltung wird gehalten nach dem Skript von Prof. Dr. Sven Rahmann. Die von Dipl.-Inf. Dominik Kopczynski erstellten Übungsaufgaben wurden zum Teil übernommen.
Übungsblätter
Blatt 1, Blatt 2, Blatt 3, Blatt 4, Blatt 5, Blatt 6, Blatt 7, Blatt 8, Blatt 9, Blatt 10, Blatt 11, Blatt 12, Blatt 13, Blatt 14
Material zu Aufgabe 4.2
- alice.txt – deutscher Text von Alice im Wunderland vom Gutenberg-Projekt, ASCII-Alphabet
- chrM.txt – mitochondriales Chromosom des Menschen, DNA-Alphabet
- ecoli.txt – Genom von Escherichia coli
Zeitplan
- 10.10.2012 (V) Organisatorisches. Motivation und Einführung: Sequenzen sind überall. DNA, RNA, Proteine. Genetischer Code. Das Schweinegrippevirus H1N1. kA/kS-Analyse. Übungsblatt 1
- 11.10.2012 (Ü) keine Übung
- 17.10.2012 (V) Das Pattern-Matching-Problem: Grundlegende Definitionen. Naiver Algorithmus. Nichtdeterministische und deterministische endliche Automaten. Beziehung zwischen NFA und DFA für einfaches Patternmatching. Übungsblatt 2
- 18.10.2012 (Ü) erste Übung, Besprechung Blatt 1
- 24.10.2012 (V) Fortsetzung DFAs; Knuth-Morris-Pratt-, Shift-And-Algorithmus. Übungsblatt 3
- 25.10.2012 (Ü) Besprechung Blatt 2 und Aufgabe 1 von Blatt 3
- 31.10.2012 (V) Fortsetzung Shift-And-Algorithmus; Horspool-Algorithmus; Backward Nondeterministic DAWG Matching (BNDM); Übungsblatt 4
01.11.2012 (Ü)Allerheiligen- 07.11.2012 (V) Fortsetzung BNDM; erweiterte Patterns: generalisierte Strings, Gaps beschränkter Länge; Indexdatenstrukturen Suffixbaum und Suffixarray Übungsblatt 5
- 08.11.2012 (Ü) Besprechung Blatt 3 und 4
- 14.11.2012 (V) Fortsetzung Suffixbäume; Konstruktion mit Ukkonens Algorithmus; Übungsblatt 6
- 15.11.2012 (Ü) Besprechung Blatt 5
- 21.11.2012 (V) Suffixarrays (pos- und lcp-Array); Berechnung des lcp-Array; Stringprobleme auf Suffixbäumen und -arrays; Übungsblatt 7
- 22.11.2012 (Ü) Besprechung Blatt 6
- 28.11.2012 (V) Burrows-Wheeler-Transformation; Übungsblatt 8
- 29.11.2012 (Ü) Besprechung Blatt 7
- 05.12.2012 (V) Approximatives Patternmatching: Distanzmaße, Alignment, Beweis Editdistanz; Übungsblatt 9
- 06.12.2012 (Ü) Besprechung Blatt 8
- 12.12.2012 (V) Longest Common Subsequence, Edit-Graph, Anz. Alignments, Beginn Mustersuche mit Ukkonen; Übungsblatt 10
- 13.12.2012 (Ü) Besprechung Blatt 9
- 19.12.2012 (V) Forts. Ukkonen, fehlertoleranter Shift-And, Alignment mit Scores, Traceback, Free-Shift-Alignment; Übungsblatt 11
- 20.12.2012 (Ü) Besprechung Blatt 10
- 09.01.2012 (V) lokales Alignment; Alignment mit linearem Platz; Übungsblatt 12
- 10.01.2012 (Ü) Besprechung Blatt 11
- 16.01.2012 (V) Wdhl. Hirschberg; Mosaik- und Schatteneffekt; BLAST; Übungsblatt 13
- 17.01.2012 (Ü) Besprechung Blatt 12
- 23.01.2012 (V) Exaktes Pattern Matching mit Mengen von Patterns: Shift-And, Aho-Corasick; Übungsblatt 14
- 24.01.2012 (Ü) Besprechung Blatt 13
- 30.01.2012 (V)
- 31.01.2012 (Ü) Besprechung Blatt 14