Algorithmen auf Sequenzen (Spezial-/Vertiefungsvorlesung und Übung)Sommersemester 2008 [Zurück zu allen Lehrveranstaltungen] [Zurück zu meiner Homepage]
Veranstalter: Sven Rahmann (vorname.nachname[at]uni-dortmund.de)
Inhalte und Termine: hier Folien
Übungsblätter
Kommentar: Das folgende Grundproblem wird häufig schon in den Einführungsvorlesungen behandelt: Gegeben ist ein Text T und ein Muster P. Liste alle Positionen in T auf, an denen P vorkommt. Von diesem Problem gibt es viele Varianten: Statt aus einem einzenlen String kann P aus einer Menge von Strings bestehen, oder in impliziter Form gegeben sein, etwa durch einen regulären Ausdruck, oder eine sogenannte position weight matrix, oder auch durch eine kontextfreie Grammatik. Zudem suchen wir unter Umständen auch nach approximativen Vorkommen im Text (z.B. Meier vs. Mayer). Vielleicht wollen wir auch nur wissen, ob P überhaupt vorkommt, oder auch nur wie oft (ohne alle Positionen aufzulisten). Auch die Frage nach der Statistik der Anzahl der Vorkommen ist von Interesse: Angenommen, wir beobachten ein bestimmtes Muster siebzehn mal in einem bestimmten Text: Ist das überraschend oft, oder lässt sich das durch puren Zufall erklären? Die biologische Sequenzanalyse hat sich aus den Gebiet des pattern matching entwickelt, das in den 70er Jahren vor allem von theoretischen Informatikern bearbeitet wurde. Hier ist in den letzten 20 Jahren eine Fülle von (sowohl sehr einfachen als auch sehr komplizierten) Algorithmen entstanden, und es stellt sich heraus, dass die Algorithmen, "die man so kennt", in der Praxis häufig langsam sind. In der Vorlesung werden wir viele Varianten des Pattern Matching Problems ausführlich behandeln und sowohl klassische als auch die zur Zeit in der Praxis schnellsten Algorithmen kennenlernen. Es geht sowohl um on-line Algorithmen (bei denen der Text vorher nicht bekannt sein muss) als auch um index-basierte Verfahren (bei denen vorher ein Index des Textes erstellt wird). Index-basierte Verfahren sind heute sowohl bei der Analyse von Biosequenzen wichtig, als auch für web-basierte Suchmaschinen wie Google, Yahoo, und andere ein essentieller Bestandteil des Kerngeschäftes. In letzter Zeit nimmt die Bedeutung komprimierter Text-Inidizes stetig zu. Hierzu werden wir die wichtigsten Grundlagen kennenlernen und vor allem die zentrale Rolle der Burrows-Wheeler Transformation herausarbeiten. Dem ersten Teil der Vorlesung liegt das Buch Flexible Pattern Matching in Strings von Gonzalo Navarro und Mathieu Raffinot (ca. 33 Euro) zugrunde. Es wird ergänzt durch Übersichtsartikel aus der Originalliteratur, die ich in der Vorlesung angeben werde. Die Vorlesung wird von praktischen und theoretischen Übungsaufgaben begleitet, deren Bearbeitung wichtig für ein richtiges Verständnis des Sotffes ist. Die Übungen finden am Freitag im selben Raum im unmittelbaren Anschluss an die Vorlesung statt (11-12). Im Anschluss an diese Vorlesung besteht bei Begabung und Interesse die Möglichkeit, in diesem Bereich eine Diplomarbeit zu schreiben. Stand: 25.02.2008 - Sven Rahmann |