Vorlesung “Algorithmen auf Sequenzen”

Bachelor-Modul INF-Bsc-315 (Informatik, TU Dortmund)

Sommersemester 2021

Ich bin von der Universitätsallianz Ruhr weg an die Universität des Saarlandes gewechselt. Meine Vorlesungen an der TU Dortmund finden nicht mehr statt.

Einmalig biete ich Ihnen in diesem Semester an, der (englischen und umfangreicheren!) Vorlesung an der UdS zu folgen, per Zoom-Link. Bitte kontaktieren Sie mich per e-mail! Gleichzeitig stehen Ihnen die Videoaufnahmen aus dem SoSe 2020 (TU Dortmund) frei auf YouTube zur Verfügung (s.u.).

Prüfungsrelevant ist nur der Stoff vom SoSe 2020 in den Videos, sowie die Aufgben vom SoSe 2020. Ihre Prüfung muss in jedem Fall vor dem 31.03.2022 erfolgen. Danach werden keine Prüfungen mehr angeboten, auch keine Wiederholungen! Bitte melden Sie sich daher frühzeitig wegen Prüfungsterminen bei mir.

Eine Absprache mit dem Prüfungsausschuss ist notwendig.


Sommersemester 2020

Wegen der COVID-19-Situation findet die Vorlesung ausschließlich online statt. Der Vorlesungsinhalt wird per Video zur Verfügung gestellt. Zu den Kontaktzeiten werden online Fragen beantwortet und Übungsaufgaben gemeinsam besprochen und gelöst, sowie Miniprojekte in Angriff genommen. Dabei wird vorausgesetzt, dass die jeweils genannten Vorlesungsvideos bereits bekannt sind!

Vorlesung: Videos, freie Zeiteinteilung. Das Vorlesungsvideo muss aber vor der entsprechenden Kontaktzeit gesehen worden sein!
Kontaktzeiten: jeweils Donnerstags 08:30-10:00 per Big Blue Button. Den Zugangslink und das Passwort erhalten Sie nach Anmeldung im LSF.
Material: Skript-Entwurf
Prüfungen: 4 ECTS-Punkte; mündlich. Nächste Termine: 12.04.2021, weitere nach Vereinbarung. Die meisten Termine gibt es kurz nach Veranstaltungsende; spätere Termine erst, wenn sich genug Interssierte gemeldet haben.
Anmeldeformular: Zur Anmeldung ist kein Leistungsnachweis erforderlich. Bitte während des Corona-online-Betriebs das Formular einscannen und unterschrieben per email an den Veranstalter schicken und vorab den Termin (Uhrzeit) bestätigen lassen. Bitte die Informationen beachten!

Zur Teilnahme an den Sitzungen am Donnerstag 08:30 - 10:00 Uhr ist ein BigBlueButton-Zugangslink und ggf. ein Passwort erforderlich. Sie erhalten dies vom Veranstalter per email nach Ihrer Anmeldung im LSF.

1. Do 23.04. Videos:
Einführung, Definitionen und Begriffe;
naiver Algorithmus zur exakten Mustersuche.
Aufgaben: Blatt 1, Notizen 1.
2. Do 30.04. Videos:
Exakte Mustersuche mit nichtdeterministischen endlichen Automaten, Shift-And-Algorithmus.
Aufgaben: Blatt 2, Notizen 2.
3. Do 07.05. Videos:
Exakte Mustersuche mit deterministischen endlichen Automaten, Knuth-Morris-Pratt-Algorithmus.
Aufgaben: Blatt 3, Lösung zu 3.1 von Tom Voellmer, Notizen 3.
4. Do 14.05. Videos:
Exakte Musterusche mit sublinearen Algorithmen, Horspool-Algorithmus und BNDM.
Aufgaben: Blatt 4, Notizen 4; Benchmark von Philipp Hüttig.
5. Mi 20.05. Videos:
Algorithmen für die exakte Mustersuche mit Mengen von Mustern: verallgemeinerter Shift-And-Algorithmus, Aho-Corasick-Algorithmus.
Aufgaben: Blatt 5, Lösung zu 5.1 und 5.2 von Tom Voellmer, Notizen 5.
6. Do 28.05. Videos:
Suche nach erweiterten Mustern, Verallgemeinerungen des Shift-And-Algorithmus;
Anhang: Bitoperationen, population count.
Folien:
Suche nach erweiterten Mustern, Verallgemeinerungen des Shift-And-Algorithmus;
Anhang: Bitoperationen, population count.
Aufgaben: Blatt 6, Notizen 6.
7. Do 04.06. Videos:
Volltext-Indexdatenstrukturen: Suffixbäume, Algorithmus von Ukkonen, Anwendungen.
Aufgaben: Blatt 7, Notizen 7.
8. Mi 10.06. Videos:
Volltext-Indexdatenstrukturen: Suffixarrays, SAIS-Algorithmus, Anwendungen.
Aufgaben: Blatt 8, Notizen 8.
9. Do 18.06. Videos:
Burrows-Wheeler-Transformation (BWT), Backward Search.
Anhang: Rank-Datenstruktur für Bitsequenzen.
Aufgaben: Blatt 9, Notizen 9.
10. Do 25.06. Videos:
Distanzmaße zwischen Strings; Berechnung der Edit-Distanz und verwandter Maße.
Anhang: Die Four-Russians-Methode
Aufgaben: Blatt 10, Notizen 10.
11. Do 02.07. Videos:
Fehlertolerante Mustersuche (Ukkonen, Shift-And; Hybrid auf Volltext-Index).
Aufgaben: Blatt 11, Notizen 11.
12. Do 09.07. Videos:
Biologisches Sequenzalignment (4 Varianten).
Aufgaben: Blatt 12, Notizen 12.
13. Do 16.07. Videos:
Erweiterungen zum Sequenzalignment.
Aufgaben: Blatt 13, Notizen 13.

Inhalt (Vorlesungskommentar)

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.

Literatur

Gonzalo Navarro, Mathieu Raffinot
Flexible Pattern Matching in Strings
Cambridge University Press
ISBN: 0-521-03993-2

Dan Gusfield
Algorithms on Strings, Trees and Sequences
Cambridge University Press
ISBN: 0-521-58519-8

David Sankoff und Joseph P. Kruskal
Time Warps, String Edits, and Macromolecules
University of Chicago Press
ISBN: 1-575-86217-4
(Taschenbuchausgabe von 2000 des 1983 erschienenen Originals)

Weitere Originalliteratur (wissenschaftliche Aufsätze, “paper”), die im Lauf der Vorlesung bekannt gegeben wird.


Prüfungsleistungen

  • Bachelor-Wahlmodul (2V+1Ü; 4 LP); erweiterter Umfang für Studierende der RUB (5 CP)
  • 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.
  • 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.
  • Bei Fragen wenden Sie sich bitte per e-mail an den Veranstalter.

Algorithmic Bioinformatics, SIC, Saarland University | Privacy notice | Legal notice