Vorlesung “Algorithmen auf Sequenzen”

Zeitplan Wintersemester 2016/17

Vorlesung: Do 08:30-10:00 in OH14/304.
Übungen:   Do 12:15-13:00 in OH14/304.
Material:    Skript-Entwurf (Oktober 2014)
Prüfungen: Für das Bachelor-Modul INF-BSc-315 werden in diesem Semester nur mündliche Prüfungen angeboten.  Die erweiterte Prüfung zur Diplom-Spezialvorlesung (3V+1Ü, SpG 4,6,7) wird nur mündlich angeboten.  Es ist kein Leistungsnachweis notwendig zur Prüfungsanmeldung. Prüfungstermine stehen noch nicht fest.

Do 20.10. Vorlesung: Einführung, Vokabeln (Folien); Bitsequenzen, population count (Folien)
Übung: Blatt 1
Do 27.10. Vorlesung: Rank-Datenstruktur (Folien), Problem der Mustersuche: naiv (Folien)
Übung: Blatt 2
Do 03.11. Vorlesung: Mustersuche: NFA und Shift-And (Folien), DFA und Knuth-Morris-Pratt (Folien)
Übung: Blatt 3 mit Zusatzaufgaben
Do 10.11. Vorlesung: Sublineare Algorithmen zur Mustersuche (Horspool, BNDM; Folien).
Übung: Blatt 4
Do 17.11. Vorlesung: Mengen von Mustern (Folien), erweiterte Musterklassen (Folien).
Übung: Blatt 5
Do 24.11. Vorlesung und Übung fallen heute wegen Krankheit aus!
Do 01.12. Vorlesung: Volltext-Indexdatenstrukturen: Suffixtries und Suffixbäume (Folien)
Übung: Blatt 6
Do 08.12. Vorlesung: Suffixarrays und Anwendungen (Folien)
Übung: Blatt 7
Do 15.12. Vorlesung: SA-IS-Algorithmus zur Konstruktion von Suffixarrays (Folien s.o.)
Übung: Blatt 8
Do 22.12. Vorlesung: BWT, FM-Index (Folien)
Übung: Blatt 9
Do 12.01. Vorlesung: Hamming-Distanz, q-Gramm-Distanz, Edit-Distanz, longest common subsequence,
Berechnung der Edit-Distanz, Alignments, Anzahl verschiedener Alignments (Folien)
Übung: Blatt 10
Do 19.01. Vorlesung: Algorithmen zur fehlertoleranten Musterusche (Folien)
Übung: Blatt 11
Do 26.01. Vorlesung: Four-Russians-Methode (Folien), Alignment-Varianten (Folien)
Übung: Blatt 12
Do 02.02. Vorlesung: Sequenzalignment: Erweiterungen (Folien)
Übung: Blatt 13
Do 09.02. Vorlesung: Zusammenfassung, Fragen, Prüfungen
keine Übung!

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.

Skript

Mögliche Prüfungsleistungen im Bachelor-Wahlmodul INF-BSc-315

  • Bachelor-Wahlmodul (2V+1Ü; 4 LP), im Sommersemester 2011 (davor: SoSe 2010)
  • 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.
  • Sommersemester 2011: Prüfungen am 22.7., 12.8., 23.9. (jeweils Freitags)

Mögliche Prüfungsleistungen im Diplom (SpG 4,6,7)

  • Spezial-/Vertiefungsvorlesung (2V+2Ü bzw. 3V+1Ü; 6 LP), zuletzt im WS 2009/10.
    Sie gehört in die SpGs 4,6,7 nach DPO’01 und ist wahlweise als 2V+2Ü=6LP (Master) oder 3V+1Ü (Diplom) anrechenbar.
  • Leistungsnachweis (Schein), unbenotet; durch Besuch der Vorlesung, Bearbeiten der Übungsaufgaben zum Vorlesungsinhalt, abschließendes Gespräch zur Vorlesung
  • mündliche Fachprüfung zum Vorlesungsinhalt (zur Vorbereitung wird die Bearbeitung der Übungsaufgaben sehr empfohlen).
  • 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.

Zeitplan Sommersemester 2015

Die Vorlesung wird von Dominik Kopczynski gehalten.
Informationen finden Sie hier.


Zeitplan Wintersemester 2014/15

Vorlesung: Do 08:30-10:00 in OH14/E02. Beginn am 16.10. in der zweiten Woche!
Übungen:   Do 14:15-15:45 in OH14/E02. Beginn am 16.10. in der zweiten Woche!
Material:    Aktueller Skript-Entwurf (Oktober 2014)
Prüfungen: Für das Bachelor-Modul INF-BSc-315 werden in diesem Semester nur mündliche Prüfungen angeboten.
Die erweiterte Prüfung zur Diplom-Spezialvorlesung (3V+1Ü, SpG 4,6,7) wird nur mündlich angeboten.
Es ist kein Leistungsnachweis notwendig zur Prüfungsanmeldung.  Prüfungstermine stehen noch nicht fest.

Do 09.10. keine Vorlesung, keine Übung
Do 16.10. Organisatorisches, Einführung.
Grundbegriffe, Bitsequenzen, population count, rank-Datenstruktur
[Übung: Blatt 1, Besprechung des Übungsablaufs.]
Do 23.10. Pattern-Matching-Problem. Naiver Algorithmus. NFA- und DFA-basierte Algorithmen.
[keine Übung.]
Do 30.10. Knuth-Morris-Pratt-Algorithmus als DFA-Simulation. Effiziente Berechnung der lps-Funktion.
NFA-Simulation mit bit-parallelen Algorithmen: Shift-And, Shift-Or.
Horspool-Algorithmus. Berechnung der shift-Tabelle.
[Übung: Blatt 2, Besprechung der Lösungen zu Blatt 1.]
Do 06.11. Analyse des Horspool-Algorithmus. Teilstring-basierte Ansätze: BNDM, BDM, BOM.
Mustersuche mit erweiterten Mustern: generalisierte Strings, Gaps beschränkte Länge.
[keine Übung]
Do 13.11. Volltext-Index-Datenstrukturen: Suffixbaum, Suffixarray mit LCP-Array. Definition, Beispiele.
Naive Suffixbaumkonstruktion in quadratischer Zeit
[Übung: Blatt 3, Besprechung der Lösungen zu Blatt 2.]
Do 20.11. Suffixbaumkonstruktion in Linearzeit (Ukkonen’s Algorithmus).
Einfache Anwendungen von Suffixbäumen.
[keine Übung]
Do 27.11. Direkte Suffixarraykonstruktion in Linearzeit (Induced Sorting)
[Übung: Blatt 4, Besprechung der Lösungen zu Blatt 3.]
Do 04.12. Abschluss Induced Sorting. Anwendungen von Suffixbäumen und Suffixarrays:
längster wiederholter Teilstring, längster gemeinsamer Teilstring, kürzester eindeutiger Teilstring
[keine Übung]
Do 11.12. Anwendungen von Suffixbäumen und Suffixarrays:
Matching Statistics. Maximal Unique Matches.
[Übung: Blatt 5, Besprechung der Lösungen zu Blatt 4.]
Do 18.12. Burrows-Wheeler-Transformation: Konstruktion, Invertierung.
Anwendungen: Backward Search, bzip2
Weihnachtsferien. Frohes Fest und Guten Rutsch!
Do 08.01. Grundlagen des Sequenzvergleichs: Edit-Distanz
[Übung: Blatt 6. Besprechung der Lösungen zu Blatt 5.]
Do 15.01. globales Sequenz-Alignment: Scoring, DP-Algorithmus
Do 22.01. Der Alignment-Graph und verschiedene Alignment-Varianten
[Übung: Blatt 7. Besprechung der Lösungen zu Blatt 6.]
Do 29.01. Verbessertes semiglobales Alignment mit Ukkonen’s Algorithmus
Do 05.02. Multi-Muster-Suche: Aho-Corasick-Algorithmus, Positions-Gewichts-Matrizen
[Übung: Besprechung der Lösungen zu Blatt 7.]

Zeitplan Wintersemester 2012/13

Die Vorlesung wird von Marcel Martin gehalten.
Informationen finden Sie hier..


Zeitplan Sommersemester 2011 (Wahlmodul/B.Sc.)

Vorlesung: Do 08:30-10:00 in OH14/R104
Übungen:   Di  09:00-10:00 in OH14/R202 (Dominik Kopczynski); erster Übungstermin: Di 12.04.
Do 14:00-15:00 in OH14/R202 (Dominik Kopczynski); erster Übungstermin: Do 14.04.
Material:    Aktueller Skript-Entwurf.
Prüfungen: Für das Bachelor-Modul INF-BSc-315 werden in diesem Semester nur mündliche Prüfungen angeboten.
Die erweiterte Diplom-Spezialvorlesungsprüfung (3V+1Ü, SpG 4,6,7) wird grundsätzlich nur mündlich angeboten.
Prüfungstermine siehe unten.

 

 Do 07.04.
Organisatorisches. Motivation und Einführung: Sequenzen sind überall.
DNA, RNA, Proteine. Genetischer Code. Das Schweinegrippevirus H1N1. kA/kS-Analyse.
Einführungsfolien . Übungsblatt 1. Übungsblatt 1 (pdf).
 Di 12.04. 9:00st: Übung (Besprechung von Übungsblatt 1 vom 07.04.)
 Do 14.04.
Das Pattern-Matching-Problem: Grundlegende Definitionen.
Naiver Algorithmus. Nichtdeterministische und deterministische endliche Automaten.
Beziehung zwischen NFA und DFA für einfaches Patternmatching.
Übungsblatt 2. Übungsblatt 2 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 1 vom 07.04.)
 Di 19.04.
9:00st: Übung (Besprechung von Übungsblatt 2 vom 14.04.)
 Do 21.04.
Knuth-Morris-Pratt-Algorithmus. Effiziente Konstruktion der lps-Funktion.
Pattern-Matching mit bit-parallelen Algorithmen: Shift-And, Shift-Or.
Horspool-Algorithmus (Erwähnung von Boyer-Moore, Sunday).
Übungsblatt 3. Übungsblatt 3 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 2 vom 14.04.)
 Di 26.04.
9:00st: Übung (Besprechung von Übungsblatt 3 vom 21.04.)
 Do 28.04.
Analyse des Horspool-Algorithmus.
Teilstring-basierter Ansatz. (Nicht)deterministischer Suffixautomat.Algorithmus BNDM. Idee BDM, BOM (Suffixorakel). Erweiterte Patternklassen: Generalisierte Strings, Gaps beschränkter Länge (-x(u,v)-).
Übungsblatt 4. Übungsblatt 4 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 3 vom 21.04.)
 Di 03.05.
9:00st: Übung (Besprechung von Übungsblatt 4 vom 28.04.)
 Do 05.05.
Vorteil von Indexstrukturen: Suchzeit nur O(|Pattern|) statt O(|Text|).
Suffixbaum: Definition, linearer Platzbedarf. Suffixarray: pos, rank, lps; d-Intervall.
Übungsblatt 5. Übungsblatt 5 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 4 vom 28.04.)
 Di 10.05.
9:00st: Übung (Besprechung von Übungsblatt 5 vom 05.05.)
 Do 12.05.
Suffixbaumkonstruktion in Linearzeit mit Ukkonen’s Algorithmus.
Berechung von lcp in Linearzeit aus pos.
Verschiedene Stringprobleme und Lösungen auf Suffixbaum und Suffixarray.
Übungsblatt 6. Übungsblatt 6 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 5 vom 05.05.)
 Di 17.05.
9:00st: Übung (Besprechung von Übungsblatt 6 vom 12.05.)
 Do 19.05.
Mustersuche mit Suffixbaum und Suffixarray.
Burrows-Wheeler-Transformation (BWT). Anwendung auf Kompression: bzip2.
Backward Search mit Suffixarray und BWT.
Übungsblatt 7. Übungsblatt 7 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 6 vom 12.05.)
 Di 24.05.
9:00st: Übung (Besprechung von Übungsblatt 7 vom 19.05.)
 Do 26.05.
Distanzmaße (Hammingdistanz, Editdistanz). Rekurrenz zur Edit-Distanz (Beweis).
Übungsblatt 8. Übungsblatt 8 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 7 vom 19.05.)
 Di 31.05.
9:00st: Übung (Besprechung von Übungsblatt 8 vom 26.05.)
 Do 02.06.
Christi Himmelfahrt: Wegen Feiertag fällt die Übung am Donnerstag aus.
Die Donnerstagsgruppe kann in die Dienstagsgruppe kommen.
Übungsblatt 9. Übungsblatt 9 (pdf).
 Di 07.06.
9:00st: Übung (Besprechung von Übungsblatt 9 vom 02.06.)
 Do 09.06.
Alignments = Pfade durch den Edit-Graphen. Anzahl von Alignments.
Approximative Mustersuche: Ukkonen.
Übungsblatt 10. Übungsblatt 10 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 9 vom 02.06.)
 Di 14.06.
9:00st: Übung (Besprechung von Übungsblatt 10 vom 09.06.)
 Do 16.06.
Approximative Mustersuche: Shift-And.
Paarweises Sequenzalignment: global, semi-global, lokal, free gaps. Scorematrizen.
Übungsblatt 11. Übungsblatt 11 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 10 vom 09.06.)
 Di 21.06. 9:00st: Übung (Besprechung von Übungsblatt 11 vom 16.06.)
 Do 23.06.
Fronleichnam: Wegen Feiertag fällt die Übung am Donnerstag aus.
Die Donnerstagsgruppe kann in die Dienstagsgruppe kommen.
Übungsblatt 12. Übungsblatt 12 (pdf).
 Di 28.06. 9:00st: Übung (Besprechung von Übungsblatt 12 vom 23.06.)
 Do 30.06.
Paarweises Sequenzalignment (allgemeine Gapkosten, affine Gapkosten, Backtracing in linearem Platz).
Übungsblatt 13. Übungsblatt 13 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 12 vom 23.06.)
 Di 05.06.
9:00st: Übung (Besprechung von Übungsblatt 13 vom 30.06.)
 Do 07.07.
Textmodelle (M00, M0, M1, Mk, Markovmodelle variabler Ordnung, allg. Modelle mit endlichem Gedächtnis).
Simulation von Zufallstexten (Ziehen aus Verteilungen mit linearer/binärer Suche, Aliasmethode).
Übungsblatt 14. Übungsblatt 14 (pdf).
14:00ct: Übung (Besprechung von Übungsblatt 13 vom 30.06.)
 Di 12.07.
9:00st: Übung (Besprechung von Übungsblatt 14 vom 07.07.)
 Do 14.07.
Maximum-Likelihood-Parameterschätzung von einfachen Textmodellen.
HMMs.
14:00ct: Übung (Besprechung von Übungsblatt 14 vom 07.07.)

 

 



Zeitplan Sommersemester 2010 (Wahlmodul/B.Sc.)

Termin und Raum: Vorlesung Mo 8:30-10:00 in OH14/R104, Übungen Mi 8:30-10:00 in zweiwöchentlich in OH14/R104.
Bitte die genauen Übungstermine im Zeitplan beachten!
Dieser Zeitplan wird im Verlauf des Sommersemesters aktualisiert.
Aktueller Skript-Entwurf.

 

 Mo 12.04.
Organisatorisches. Motivation und Einführung: Sequenzen sind überall.
DNA, RNA, Proteine. Genetischer Code. Das Schweinegrippevirus H1N1. kA/kS-Analyse.
Übungsblatt 1. Einführungsfolien.
 Mo 19.04.
Das Pattern-Matching-Problem: Grundlegende Definitionen.
Naiver Algorithmus. Nichtdeterministische und deterministische endliche Automaten.
Knuth-Morris-Pratt-Algorithmus.
Übungsblatt 2.
 Mi 21.04.
Übung 1 (Besprechung von Übungsblatt 1 vom 12.04.)
 Mo 26.04.
Effiziente Konstruktion der lps-Funktion.
Horspool-Algorithmus, kurz: Boyer-Moore, Sunday
Pattern-Matching mit bit-parallelen Algorithmen: Shift-And, Shift-Or.
 Mi 28.04.
Übung 2 (Besprechung von Übungsblatt 2 vom 19.04.)
 Mo 03.05.
in E04!
Teilstring-basiertes Pattern-Matching: BNDM.
Genregulation. Transkriptionsfaktoren.
Modellierung von Transkriptionsfaktorbindestellen mit PWMs. Suche nach TFBSen.
Übungsblatt 3.
 Mo 10.05.
DNA-Microarrays. DNA-Energiemodelle.
DNA-Sequenzdesign für Microarrays und nanotechnologische Anwendungen
 Mi 12.05.
Übung 3 (Besprechung von Übungsblatt 3 vom 03.05.)
 Mo 17.05.
Modelle für Zufallssequenzen (i.i.d, Markovketten, allgemeine Modelle mit endlichem Gedächtnis)
3 Aufgaben: Simulieren, Wahrscheinlichkeit berechnen, Parameter schätzen.
Übungsblatt 4.
 Mo 24.05.
 — Pfingstmontag —
 Mo 31.05.
HMMs, Definition. Algorithmen auf HMMs: Forward, Viterbi
 Mi 02.06.
Übung 4
 Mo 07.06.
Algorithmen auf HMMs: Posterior decoding mit Hilfe von forward- und backward-Wahrscheinlihckeiten. Ergänzungen: stumme Zustände, sehr kleine Wahrscheinlichkeiten (Logarithmieren oder Skalieren), Verweildauer in Zuständen (geometrische Verteilung, negative Binomialverteilung).
Übungsblatt 5.
 Mo 14.06.
paarweiser Sequenzvergleich: Hamming-Distanz, q-gram-Distanz, Edit-Distanz, longest common subsequence. Dynamic-Programming-Algorithmus zur Edit-Distanz.
 Mi 16.06.
Übung 5
 Mo 21.06.
Edit-Graph. Algorithmus von Ukkonen. k-Fehler-NFA.
Übungsblatt 6.
 Mo 28.06.
Paarweises Sequenzalignment. Traceback.
Scorematrizen, Gapkosten.
Alignment-Graph. Verschiedene Arten von Alignments.
 Mi 30.06.
Übung 6
 Mo 05.07.
Indexstrukturen: Suffixbaum, Suffixarray
 Mo 12.07.
Einfache Konstruktion von Suffixbäumen und Suffixarrays.
Linearzeit-Konstruktion von Suffixbäumen: Algorithmus von Ukkonen.
Anwendungen von Suffixbäumen und Suffixarrays.
Übungsblatt 7.
 Mo 19.07.
Weitere Anwendungen von Suffixbäumen und Suffixarrays.
Burrows-Wheeler-Transformation, bzip2.
 Mi 21.07.
Übung 7