Specialized course, M.Sc. Bioinformatics, Saarland University.
Elective course, M.Sc. Computer Science and related, Saarland University.
|Prerequisites||B.Sc. in Bioinformatics or CS, no special requirements.|
|Credits||9 ECTS credits|
|Required time||4V+2Ü (4 hours of lectures, 2 hours of tutorials per week)|
|Registration||specific to each semester, see below|
The following topics will be covered in the course; additional topics may be included, depending on time and current events.
Scroll down for course schedule and assignments.
Because of the ongoing CoViD-19 pandemic, this lecture and its associated tutorials will be online only and delivered via Zoom. Lecture recordings and exercise sheets will be linked on this page.
We will discuss the exercises together as a group. For this to work effectively, it is expected that you have watched the lectures or recordings and thought about the problems each week!
|Instructor||Prof. Dr. Sven Rahmann|
|Lectures||Tue 12:30-14:00 and Thu 08:30-10:00 each week via Zoom. These lectures will be recorded.|
|Exercises||either (A) Tue 14:15-15:45 or (B) Wed 08:30-10:00|
|Exams||9 ECTS credits. Dates and details TBD. General information on exams (in German)|
|Registration||Register at the CMS until Friday April 16.|
|Note||Summer 2021 is a virtual online semester. Lectures will be delivered via Zoom. To obtain the Zoom link, please register for the course and then look at the provided link in the CMS.|
Note 1: Video recordings of the lectures are only available in the CMS for registered students.
Note 2: Links for assignment submission are sent out by email to registered students. They are also available in the CMS if you lost the email.
|Tue 13.04.||Exact pattern matching: Naive, Horspool. (Adminstrative issues.)||Slides; Admin|
|Thu 15.04.||Automata-based algorithms (NFA: Shift-And; DFA: Knuth-Morris-Pratt)||Slides|
|Assignment 1, submit via github classroom, invitation sent by email|
|Tue 20.04.||Bit-parallel algorithms: BNDM; more general patterns||Slides|
|Thu 22.04.||A primer on efficient Python programming: Counting motif occurrences in genomes||Slides|
|Assignment 2, submit via github classroom, invitation sent by email|
|Tue 27.04.||Full-text index data structures: Suffix trees, Ukkonen’s algorithm.||Slides|
|Thu 29.04.||Ukkonen’s algorithm: Skip/count trick analysis. Suffix arrays and enhancements (lcp).||Slides|
|Assignment 3, submit via github classroom, invitation sent by email|
|Tue 04.05.||Applications of suffix arrays and linear-time lcp construction (Kasai’s algorithm)||Slides above|
|Thu 06.05.||Linear-time suffix array construction: SAIS algorithm||Slides|
|Assignment 4, submit via github classroom, invitation sent by email|
Gonzalo Navarro, Mathieu Raffinot
Flexible Pattern Matching in Strings
Cambridge University Press
Algorithms on Strings, Trees and Sequences
Cambridge University Press
David Sankoff und Joseph P. Kruskal
Time Warps, String Edits, and Macromolecules
University of Chicago Press
Additional research papers may be provided during the lectures.