This is an old revision of the document!
Sequenzen sind allgegenwärtig. Texte und Programme, Gene und Proteine, Polygonzüge, Sprach- und Bildsignale und digitalisiertes Vogelzwitschern werden dargestellt als Zeichenfolgen über einem endlichen Alphabet. Entsprechend vielfältig sind die algorithmischen Fragestellungen. Oft ist dabei der Datenumfang sehr groß, so dass die algorithmische Komplexität von entscheidender praktischer Bedeutung ist.
In der Vorlesung werden Algorithmen zum effizienten Vergleich von Sequenzen und zur Suche exakter und approximativer Muster in Sequenzen behandelt. Viele dieser Algorithmen sind durch bioinformatische Fragestellungen motiviert. Sie finden jedoch auch Anwendungen in anderen Bereichen wie z.B. der Textverarbeitung und der Datenkompression.
Achtung: Die Veranstaltung findet live per Videokonferenz statt. Informationen hierzu werden kurz vor Beginn am 20.4.2020 an alle eingetragenen Teilnehmer*innen verschickt.
Abgabeschluss der wöchentlichen Übungsaufgaben ist jeweils Montags 12:00 Uhr. Gleichzeitig wird ein neuer Übungszettel auf dieser Seite veröffentlicht werden. Abgaben müssen direkt per E-mail an die jeweiligen Tutoren geschickt werden.
Termin | Tutorin | Raum | eKVV |
Di 16-18 | Marilia Dias Vieira Braga | | 392106 |
Di 16-18 | Rebecca Pfeil | – | |
Mi 16-18 | Leonie Brockmann | – |
Woche | Datum | Thema | Abschnitt im Skript | Übungszettel | Sonstiges |
| | ||||
| | ||||
17 | 21./23.04.2020 | Di: Einleitung, Logistik Do: Wh. Grundlagen | 1 2 | ||
18 | 28./30.04.2020 | Di: Def. Metriken auf Sequenzen Do: Berechnung der Edit-Distanz | 3.1-3.5 3.6 | ||
19 | 05./07.05.2020 | Di: Die q-gram-Distanz Do: Die Maximal-Matches-Distanz, Filtern | 3.7 3.8, 3.9 | ||
20 | 12./14.05.2020 | Di: Def. paarweises Alignment, Alignment-Score Do: Alignment-Graph und universeller Algorithmus | 4.1, 4.2 4.3, 4.4 | ||
21 | 19./ | Di: Alignment-Typen, Gapkosten Do: – | 4.5, 4.6 – | ||
22 | 26./28.05.2020 | Di: Fortgeschrittene Alignment-Themen I Do: Fortgeschrittene Alignment-Themen II | 5.1, 5.2 5.3, 5.4 | ||
23 | 02./04.06.2020 | Di: Paarweises Alignment in der Praxis Do: Def. Suffixbäume, WOTD-Algorithmus | 6 7.1-7.6 | ||
24 | 09./ | Di: Anwendungen von Suffixbäumen Do: – | 7.7 – | ||
25 | 16./18.06.2020 | Di: Suffixarrays Do: Burrows-Wheeler-Transformation | 8 9 | ||
26 | 23./25.06.2020 | Di: Def. Multiples Alignment, NP-Completeness Do: Exakte Algorithmen für SP-Alignment | 10 11.1-11.3 | ||
27 | 30.6./02.07.2020 | Di: Heuristiken für SP-Alignment Do: Baumalignment, Genomalignment | 11.4, 11.5 12, 13 | ||
28 | 07./09.07.2020 | Di: Allgemeine Wiederholung, Fragen Do: Klausur (?) | – – |