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 Veranstaltungsseite zu Algorithmen auf Sequenzen aus dem Wintersemester 2014/2015.

Weitere Infos finden Sie in der Modulbeschreibung.

Skript

Aktueller Skript-Entwurf – vom WiSe 14/15

Folien

Übungsblätter

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: 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:

Zeitplan

  • 09.04.2015 (V) Organisatorisches. Motivation und Einführung: Bitsequenzen und -opertionen. Popcount und Rank-Datenstruktur.
  • 14.04.2015 (Ü) erste Übung, Besprechung von 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 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 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 Blatt 4
  • 07.05.2015 (V) Volltext-Indizes: Suffix-Trie, Suffix-Tree, Ukkonen-Algorithmus
  • 12.05.2015 (Ü) Besprechung von 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 Blatt 6
  • 28.05.2015 (V) Volltext-Indizes: Suffix-Array, SAIS-Algorithmus - Teil 2
  • 02.06.2015 (Ü) Besprechung von 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 Blatt 8
  • 18.06.2015 (V) Fehlertolerantes Pattern-Matching, globales/semiglobales Alignment
  • 23.06.2015 (Ü) Besprechung von Blatt 9
  • 25.06.2015 (V) Fehlertolerante Shift-And / Backward Search; Tracebackverfahren; verschiedene Alignment-Varianten, Affine Gapkosten
  • 30.06.2015 (Ü) Besprechung von Blatt 10
  • 02.07.2015 (V) Alignments mit Einschränkungen, Alignment mit linearem Platzbedarf, Alignment Statistik, Four-Russians Methode
  • 07.07.2015 (Ü) Besprechung von Blatt 11
  • 09.07.2015 (V) Zusammenfassung, Frage & Antwort, Vorbereitung auf mündl. Prüfungen
  • 14.07.2015 (Ü) Besprechung von Blatt 12
  • 16.07.2015 (V) fällt aus
 
Last modified: 2015-09-08 15:53 (external edit)
DokuWikiRSS-Feed