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.
Aktueller Skript-Entwurf – vom WiSe 14/15
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)
Veranstalter: Dominik Kopczynski
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: