Vorlesung: Mi 08:30-10:00 in OH14/304
Übung: Do 14:15-15:00 in OH12/1.056
Prüfung (Modul INF-Bsc-315 in Informatik, Angewandter Informatik):
Mündliche Prüfung von 20-30 Minuten Dauer oder Klausur von 90 Minuten Dauer Die genaue Prüfungsform wird abhängig von der Teilnehmerzahl kurz nach Vorlesungsbeginn festgelegt.
Zur Anmeldung den Vordruck für die Prüfungsanmeldung ausfüllen, bei Frau Jankord (OH14 / R2.39) einen Termin/Uhrzeit geben lassen, von Prof. Rahmann oder Frau Jankord unterschreiben lassen; wird von Frau Jankord zur Prüfungsverwaltung geschickt.
Material: Skript und Folien werden auf dieser Seite verlinkt.
| Datum | Themen |
|---|---|
| V Mi 10.10. | Einführung und Begriffe. Bitsequenzen und population count. |
| Ü Do 11.10. | Ausgabe Blatt 1. |
| V Mi 17.10. | Rank-Datenstruktur. Problem der Mustersuche: naive Lösung. Mustersuche mit NFAs: Shift-And. |
| Ü Do 18.10. | Besprechung Blatt 1. Ausgabe Blatt 2. |
| V Mi 24.10. | Mustersuche: DFAs und Knuth-Morris-Pratt; Sublineare Algorithmen (Horspool) |
| Ü Do 25.10. | Besprechung Blatt 2. Ausgabe Blatt 3. |
| V Mi 31.10. | Mustersuche: Sublineare Algorithmen (BNDM); Mengen (Multi-Shift-And) |
| Ü Do 01.11. | fällt aus (Allerheiligen) |
| V Mi 07.11. | Mustersuche: Mengen (Aho-Corasick). Erweiterte Muster. |
| Ü Do 08.11. | fällt aus (Begutachtung) |
| V Mi 14.11. | Volltext-Indexdatenstrukturen: Suffixtries und Suffixbäume. |
| Ü Do 15.11. | Besprechung Blatt 3. Ausgabe Blatt 4. |
| V Mi 21.11. | Suffixarrays und ihre Konstruktion (SAIS). |
| Ü Do 22.11. | Besprechung Blatt 4. Ausgabe Blatt 5. |
| V Mi 28.11. | Suffixarray, LCP-Array und Anwendungen. |
| Ü Do 29.11. | Besprechung Blatt 5. Ausgabe Blatt 6. |
| V Mi 05.12. | BWT, bzip2, FM-Index, Wavelet Trees. |
| Ü Do 06.12. | Besprechung Blatt 6. Ausgabe Blatt 7. |
| V Mi 12.12. | Distanzen auf Strings, Edit-Sequenzen, globale Alignments. |
| Ü Do 13.12. | Besprechung Blatt 7. Ausgabe Blatt 8. |
| V Mi 19.12. | (fällt wegen Krankheit aus) |
| Ü Do 20.12. | (fällt wegen Krankheit aus) |
| Weinachtsferien, Jahreswechsel | |
| V Mi 09.01. | Algorithmen zur fehlertoleranten Musterusche. Four-Russians-Methode. |
| Ü Do 10.01. | Besprechung Blatt 8. Ausgabe Blatt 9. |
| V Mi 16.01. | Sequenzalignment: Algorithmen (Scoring, Varianten) |
| Ü Do 17.01. | Besprechung Blatt 9. Ausgabe Blatt 10. |
| V Mi 23.01. | Sequenzalignment: Erweiterungen |
| Ü Do 24.01. | Besprechung Blatt 10. Ausgabe Blatt 11. |
| V Mi 30.01. | Zusammenfassung, Wiederholung und Fragen. |
| Ü Do 31.01. | Besprechung Blatt 11. Allgemeine Fragen. |
Finaler Zeitplan, 09.01.2019.
Gonzalo Navarro, Mathieu Raffinot
Flexible Pattern Matching in Strings
Cambridge University Press
ISBN: 0-521-03993-2
Das folgende Problem ist aus den Einführungsvorlesungen bekannt: 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 einzelnen 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 Varianten des Pattern Matching Problems ausführlich behandeln und sowohl klassische als auch die zur Zeit in der Praxis schnellsten Algorithmen kennen lernen. 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 oder Bing ein essentieller Bestandteil des Kerngeschäfts.
In letzter Zeit nimmt die Bedeutung komprimierter Text-Inidizes stetig zu. Hierzu werden wir die wichtigsten Grundlagen kennen lernen 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 zu Grunde. Es wird ergänzt durch Übersichtsartikel aus der Originalliteratur, die ich in der Vorlesung angeben werde. Zur Vorlesung wird ein Skript zur Verfügung gestellt.
Die Vorlesung wird von praktischen und theoretischen Übungsaufgaben begleitet, deren Bearbeitung wichtig für ein richtiges Verständnis des Stoffs ist. Im Anschluss an diese Vorlesung besteht bei Begabung und Interesse die Möglichkeit, in diesem Bereich eine Abschlussarbeit zu schreiben.
und Datenschutz
Diese Webseite dient ausschließlich der Bekanntmachung von Vorlesungsinhalten einer Veranstaltung an der TU Dortmund von
Prof. Dr. Sven Rahmann
Institut für Humangenetik / Genominformatik
Medizinische Fakultät der Universität Duisburg-Essen
Universitätsklinikum Essen
Hufelandstr. 55
45147 Essen
Diese Webseite wird auf gitlab.io gehostet, und der Hoster kann Informationen über ihr Surfverhalten sammeln (Cookies, etc.). Für ausgehende Links wird keine Haftung übernommen. Obwohl sich der Autor um eine exakte Darstellung der Inhalte bemüht, wird für die Korrektheit der Angaben keine Garantie gegeben; eine Haftung ist ausgeschlossen.
Wir fragen Sie auf dieser Webseite nach keinen persönlichen Informationen. Wir nutzen externe JavaScript Bibliotheken, um diese Seite schöner zu gestalten. Der Hoster gitlab.io kann durch Cookies o.ä. ihr Surfverhalten verfolgen. Ausgehende Links können auf andere Webseiten verweisen, deren Datenschutzpolitik wir nicht kennen.