====== Algorithmen auf Sequenzen ====== Das Grundproblem vieler Sequenzanalysen sei folgendermaßen beschrieben: "Gegeben sei ein Text T und ein Muster (Pattern) P. Gesucht ist: kommt P in T überhaupt vor? Wenn ja, wie oft und an welchen Positionen?" In der Vorlesung werden einige prominente Methoden des Pattern-Matching Problems vorgestellt und besprochen (u.a. naives Pattern-Matching, Knuth-Morris-Pratt, Horspool, Shift-And). Da die meisten Algorithmen nur ein Pattern in Betracht ziehen, werden ebenfalls Methoden für eine Menge von Pattern vorgestellt (Aho-Corasick, Shift-And). Auch der Umgang mit verallgemeinerten Pattern (Wildcards, Gaps), wird erläutert. Gemeinsam haben all diese Algorithmen, dass sie den Text sequenziell durchgehen und dementsprechend die Laufzeit linear von der Länge des Textes abhängt. Diese kann mit unter sehr groß werden, siehe gesamtes WWW, Humangenom, Quellcode des Linuxkernels, etc. Durch eine Vorverarbeitung kann der Text indiziert werden, so dass die Laufzeit nur noch logarithmisch von der Länge des Textes (Suffixarray) oder sogar nur noch von der Länge des Patterns abhängt (Suffixbaum, Burrows-Wheeler-Transformation, Backward-Search). Da jedoch eine exakte Mustersuche meist unzureichende Ergebnisse liefert (Suche nach 'Meier', 'Meyer', 'Maier' oder 'Mayer'), wurden Verfahren entwickelt, die fehlertolerant nach Teilsequenzen suchen. Dabei kann wiederrum zwischen Methoden unterschieden werden, die unter Einhaltung von Einheitskosten nach Teilsequenzen mit den wenigsten Editierungsoperationen suchen (fehlertoleranter Shift-And, fehlertolerante Backward-Search) oder die eine Scoring-Tabelle mit Scores für die jeweiligen Edit-Operationen einbeziehen (globales Alignment, semiglobales Alignment, lokales Alignment). Diese Veranstaltung findet im Sommesemester 2015 statt. Weiterführende Informationen, sowie verwendete Literatur finden sich auf der [[http://www.rahmannlab.de/lehre/v-algo-seq|Veranstaltungsseite zu Algorithmen auf Sequenzen aus dem Wintersemester 2014/2015]]. Weitere Infos finden Sie in der [[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Bachelor_Inf/INF/INF-W/INF-BSc-315.pdf|Modulbeschreibung]]. ===== Skript ===== [[http://ls11-www.cs.tu-dortmund.de/people/rahmann/algoseq.pdf|Aktueller Skript-Entwurf]] -- vom WiSe 14/15 ===== Folien ===== * 0. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien00.pdf|Organisatorisches]] (Stand: 09.04.15) * 1. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien01.pdf|Bitsequenzen]] (Stand: 09.04.15) * 2. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien02.pdf|Pattern-Matching]] (Stand: 13.04.15) * 3. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien03.pdf|Pattern-Matching mit einer Patternmenge]] (Stand: 29.04.15) * 4. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien04.pdf|Erweiterte Patternklassen]] (Stand: 02.05.15) *5. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien05.pdf|Volltext-Indizes]] (Stand: 20.05.15) *6. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien06.pdf|Volltext-Indizes - Teil 2]] (Stand: 28.05.15) *7. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien07.pdf|Volltext-Indizes - Teil 3]] (Stand: 12.06.15) *8. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien08.pdf|Fehlertolerantes Pattern-Matching]] (Stand: 26.06.15) *9. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien09.pdf|Paarweises Sequenzalignment]] (Stand: 03.07.15, aktualisiert) *10. [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_folien10.pdf|Vorbereitung zur Prüfung]] (Stand: 09.07.15) ===== Übungsblätter ===== * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt01.pdf|Blatt 1]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt02.pdf|Blatt 2]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt03.pdf|Blatt 3]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt04.pdf|Blatt 4]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt05.pdf|Blatt 5]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt06.pdf|Blatt 6]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt07.pdf|Blatt 7]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt08.pdf|Blatt 8]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt09.pdf|Blatt 9]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt10.pdf|Blatt 10]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt11.pdf|Blatt 11]] * [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt12.pdf|Blatt 12]] ===== Termine ===== Vorlesung: Do., 10:15 -11:45 Uhr in OH14 / R3.04 (erste Vorlesung: 09.04.2015) Übung: Di., 12:15 -13:00 Uhr. in OH14 / R3.04 (erste Übung: 14.04.2015) ===== Kontakt ===== Veranstalter: [[:staff:kopczynski|Dominik Kopczynski]] ===== Modulprüfung ===== Eine 20-30-minütige mündliche Prüfung. Der Prüfungstermin kann individuell bestimmt werden. Bitte diesbezüglich eine E-Mail an den Veranstalter schreiben. Die Modulnummer ist **Inf-BSc-315**. Vordrucke finden Sie hier: * [[http://www.tu-dortmund.de/uni/studierende/pruefungsangelegenheiten/infopoint_team1/AnmeldungMdl_BSc_MSc_Inf_AI.pdf|Anmeldung für mündl. Prüfung]] * [[http://www.tu-dortmund.de/uni/studierende/pruefungsangelegenheiten/infopoint_team1/Abmeldevordruck_MSc-BSc.pdf|Abmeldung von Prüfungen]] ===== Zeitplan ===== * 09.04.2015 **(V)** Organisatorisches. Motivation und Einführung: Bitsequenzen und -opertionen. Popcount und Rank-Datenstruktur. * 14.04.2015 **(Ü)** erste Übung, Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt01.pdf|Blatt 1]] * 16.04.2015 **(V)** Naiver Pattern-Matching Algorithmus: Laufzeitanalyse; Knuth-Morris-Pratt Algorithmus: Mustersuche; Shift-And Algorithmus: Mustersuche * 21.04.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt02.pdf|Blatt 2]] * 23.04.2015 **(V)** Horspool-Algorithmus: Mustersuche, Laufzeitanalyse; BNDM-Algorithmus: Mustersuche; Mustersuche auf Menge von Mustern: Multi-Shift-And * 28.04.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt03.pdf|Blatt 3]] * 30.04.2015 **(V)** Mustersuche auf Menge von Mustern: Aho-Corasick; Erweiterte Patternklassen: Wildcards, Gaps beschränkter Länge, Optionale Zeichen * 05.05.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt04.pdf|Blatt 4]] * 07.05.2015 **(V)** Volltext-Indizes: Suffix-Trie, Suffix-Tree, Ukkonen-Algorithmus * 12.05.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt05.pdf|Blatt 5]] * 14.05.2015 **(V)** fällt aus, Christi Himmelfahrt * 19.05.2015 **(Ü)** keine Übung * 21.05.2015 **(V)** Volltext-Indizes: Suffix-Tree, Ukkonen-Algorithmus - Teil 2; Suffix-Array, SAIS-Algorithmus * 26.05.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt06.pdf|Blatt 6]] * 28.05.2015 **(V)** Volltext-Indizes: Suffix-Array, SAIS-Algorithmus - Teil 2 * 02.06.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt07.pdf|Blatt 7]] * 04.06.2015 **(V)** fällt aus, Fronleichnam * 09.06.2015 **(Ü)** keine Übung * 11.06.2015 **(V)** Burrows-Wheeler-Transformation, Backward Search * 16.06.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt08.pdf|Blatt 8]] * 18.06.2015 **(V)** Fehlertolerantes Pattern-Matching, globales/semiglobales Alignment * 23.06.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt09.pdf|Blatt 9]] * 25.06.2015 **(V)** Fehlertolerante Shift-And / Backward Search; Tracebackverfahren; verschiedene Alignment-Varianten, Affine Gapkosten * 30.06.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt10.pdf|Blatt 10]] * 02.07.2015 **(V)** Alignments mit Einschränkungen, Alignment mit linearem Platzbedarf, Alignment Statistik, Four-Russians Methode * 07.07.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt11.pdf|Blatt 11]] * 09.07.2015 **(V)** Zusammenfassung, Frage & Antwort, Vorbereitung auf mündl. Prüfungen * 14.07.2015 **(Ü)** Besprechung von [[/people/kopczyns/lehre/AAS/SS15/aas_sose15_blatt12.pdf|Blatt 12]] * 16.07.2015 **(V)** fällt aus /* * 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]] * 01.11.2012 **(Ü)** 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 */