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.

Aktueller Skript-Entwurf – zuletzt aktualisiert am 24.01.2013

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)

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.

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

• 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