Vorlesung + Uebung
Algorithmen auf Sequenzen

Veranstalter: Prof. Dr. Sven Rahmann, TU Dortmund
Zeit und Ort: Montags 10-12, Freitags 10-12; in OH16, E07.


Mo 07.04.  Einfuehrung. Motivation. Definitionen. Das Pattern-Matching Problem.
	   Der naive Algorithmus. Ein DFA-Algorithmus.
           Ausgabe von Blatt 1
Fr 11.04.  Der Knuth-Morris-Pratt (KMP) Algorithmus.
           Prefix-, Suffix- und Teilstring-basiertes pattern matching.
           Besprechung von Blatt 1.

Mo 14.04.  Varianten des Boyer-Moore-Algorithmus (BM, Horspool, Sunday).
           Analyse des Sunday-Algorithmus.
           Ausgabe von Blatt 2+3.
Fr 18.04.  (faellt aus)

Mo 21.04.  (faellt aus)
Fr 25.04.  Teilstring-basierte Verfahren: BNDM, BDM.
           Besprechung von Blatt 2+3.

Mo 28.04.  Das Teilstring-Orakel. Backward Oracle Matching (BOM).
           Der Rabin-Karp-Algorithmus. q-grams.
Fr 02.05.  Verallgemeinerte  Strings: Zeichenklassen in Pattern und Text
           Besprechung von Blatt 4.

Mo 05.05.  Verallgemeinerte Strings: Gaps beschraenkter Laenge
Fr 09.05.  Verallgemeinerte Strings: Optionale und wiederholbare Zeichen

Mo 12.05.  (faellt aus, Pfingsten)
Fr 16.05.  Mengen von Strings: Aho-Corasick als KMP-Erweiterung

Mo 19.05.  Mengen von Strings: Adaption weiterer Algorithmen
Fr 23.05.  regulaere Ausdruecke: Parsen, Thompson-Automat und Simulation

Mo 26.05.  (faellt aus, JFRC Konferenz)
Fr 30.05.  regulaere Ausdruecke: Glushkov-Automat und Simulation

Mo 02.06.  regulaere Ausdruecke: 
           Adaption von Suffix-/Teilstring-basierten Verfahren
Fr 06.06.  Approximative Teilstringsuche: DP

Mo 09.06.  Approximative Teilstringsuche: NFAs
           Anwendung: Mapping von DNA-Reads auf Genome
Fr 13.06.  Approximative Teilstringsuche: Bit-parallele Implementierungen
           Adaption von Suffix-/Teilstringbasierten Verfahren, ABNDM

Mo 16.06.  Alignments: lokal, global, Mischformen;
           Alignment-Algorithmen als Wege maximalen Gewichts in Graphen
           normalisiertes Alignment
Fr 20.06.  allgemeine, affine, konvexe Gapkosten
            PWM-Modell und Anwendungen

Mo 23.06.  Pattern-Statistiken mit DFAs: PAAs
Fr 27.06.  Weitere Anwendungen von PAAs. Uebungen.

Mo 30.06.  Indexbasierte Verfahren: q-grams, Suffixbaeume, Suffixarrays
Fr 04.07.  Suffixarrays und Enhanced Suffixarrays

Mo 07.07.  Konstruktion von Suffixbaeumen und Suffixarrays
Fr 11.07.  Konstruktion von Enhanced Suffix Arrays

Mo 14.07.  Anwendugen von Suffixbaeumen und Suffix-Arrays
           Burrows-Wheeler Transformation
Fr 18.07.  Zusammenfassung & Abschluss