====== Algorithmen auf Sequenzen ======

Diese Veranstaltung findet im Wintersemester 2012/2013 statt. Orientieren Sie sich auch an der [[http://www.rahmannlab.de/lehre/v-algo-seq|Veranstaltungsseite zu Algorithmen auf Sequenzen aus dem Sommersemester 2011]].

===== Skript =====

[[http://ls11-www.cs.tu-dortmund.de/people/martin/algoseq/algoseq.pdf|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: [[:staff:martin|M. Martin]]

Die Veranstaltung wird gehalten nach dem Skript von [[http://www.rahmannlab.de/people/rahmann|Prof. Dr. Sven Rahmann]]. Die von [[:staff:kopczynski|Dipl.-Inf. Dominik Kopczynski]] erstellten Übungsaufgaben wurden zum Teil übernommen.

===== Übungsblätter =====

[[/people/martin/algoseq/blatt01.pdf|Blatt 1]], [[/people/martin/algoseq/blatt02.pdf|Blatt 2]], [[/people/martin/algoseq/blatt03.pdf|Blatt 3]], [[/people/martin/algoseq/blatt04.pdf|Blatt 4]], [[/people/martin/algoseq/blatt05.pdf|Blatt 5]], [[/people/martin/algoseq/blatt06.pdf|Blatt 6]], [[/people/martin/algoseq/blatt07.pdf|Blatt 7]], [[/people/martin/algoseq/blatt08.pdf|Blatt 8]], [[/people/martin/algoseq/blatt09.pdf|Blatt 9]], [[/people/martin/algoseq/blatt10.pdf|Blatt 10]], [[/people/martin/algoseq/blatt11.pdf|Blatt 11]], [[/people/martin/algoseq/blatt12.pdf|Blatt 12]], [[/people/martin/algoseq/blatt13.pdf|Blatt 13]], [[/people/martin/algoseq/blatt14.pdf|Blatt 14]]

Material zu Aufgabe 4.2
  * [[/people/martin/algoseq/alice.txt|alice.txt]] -- deutscher Text von Alice im Wunderland [[http://www.gutenberg.org/ebooks/19778|vom Gutenberg-Projekt]], ASCII-Alphabet
  * [[/people/martin/algoseq/chrM.txt|chrM.txt]] -- mitochondriales Chromosom des Menschen, DNA-Alphabet
  * [[/people/martin/algoseq/ecoli.txt|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. [[/people/martin/algoseq/blatt01.pdf|Ü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. [[/people/martin/algoseq/blatt02.pdf|Übungsblatt 2]]
  * 18.10.2012 **(Ü)** erste Übung, Besprechung Blatt 1
  * 24.10.2012 **(V)** Fortsetzung DFAs; Knuth-Morris-Pratt-, Shift-And-Algorithmus. [[/people/martin/algoseq/blatt03.pdf|Ü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); [[/people/martin/algoseq/blatt04.pdf|Übungsblatt 4]]
  * <del>01.11.2012 **(Ü)**</del> Allerheiligen
  * 07.11.2012 **(V)** Fortsetzung BNDM; erweiterte Patterns: generalisierte Strings, Gaps beschränkter Länge; Indexdatenstrukturen Suffixbaum und Suffixarray [[/people/martin/algoseq/blatt05.pdf|Übungsblatt 5]]
  * 08.11.2012 **(Ü)** Besprechung Blatt 3 und 4
  * 14.11.2012 **(V)** Fortsetzung Suffixbäume; Konstruktion mit Ukkonens Algorithmus; [[/people/martin/algoseq/blatt06.pdf|Ü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; [[/people/martin/algoseq/blatt07.pdf|Übungsblatt 7]]
  * 22.11.2012 **(Ü)** Besprechung Blatt 6
  * 28.11.2012 **(V)** Burrows-Wheeler-Transformation; [[/people/martin/algoseq/blatt08.pdf|Übungsblatt 8]]
  * 29.11.2012 **(Ü)** Besprechung Blatt 7
  * 05.12.2012 **(V)** Approximatives Patternmatching: Distanzmaße, Alignment, Beweis Editdistanz; [[/people/martin/algoseq/blatt09.pdf|Übungsblatt 9]]
  * 06.12.2012 **(Ü)** Besprechung Blatt 8
  * 12.12.2012 **(V)** Longest Common Subsequence, Edit-Graph, Anz. Alignments, Beginn Mustersuche mit Ukkonen; [[/people/martin/algoseq/blatt10.pdf|Übungsblatt 10]]
  * 13.12.2012 **(Ü)** Besprechung Blatt 9
  * 19.12.2012 **(V)** Forts. Ukkonen, fehlertoleranter Shift-And, Alignment mit Scores, Traceback, Free-Shift-Alignment; [[/people/martin/algoseq/blatt11.pdf|Übungsblatt 11]]
  * 20.12.2012 **(Ü)** Besprechung Blatt 10
  * 09.01.2012 **(V)** lokales Alignment; Alignment mit linearem Platz; [[/people/martin/algoseq/blatt12.pdf|Übungsblatt 12]]
  * 10.01.2012 **(Ü)** Besprechung Blatt 11
  * 16.01.2012 **(V)** Wdhl. Hirschberg; Mosaik- und Schatteneffekt; BLAST; [[/people/martin/algoseq/blatt13.pdf|Übungsblatt 13]]
  * 17.01.2012 **(Ü)** Besprechung Blatt 12
  * 23.01.2012 **(V)** Exaktes Pattern Matching mit Mengen von Patterns: Shift-And, Aho-Corasick; [[/people/martin/algoseq/blatt14.pdf|Übungsblatt 14]]
  * 24.01.2012 **(Ü)** Besprechung Blatt 13
  * 30.01.2012 **(V)**
  * 31.01.2012 **(Ü)** Besprechung Blatt 14

/* 
Einführungsfolien . Übungsblatt 1. Übungsblatt 1 (pdf).
 Di 12.04. 	9:00st: Übung (Besprechung von Übungsblatt 1 vom 07.04.)
 Do 14.04.  
Übungsblatt 2. Übungsblatt 2 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 1 vom 07.04.)
*/