News
Exam Schedule Wed/Thu/Fri 18.20,10.Written on 17.10.23 by Sven Rahmann Please note the exam schedule for the following days that has been posted on the Materials page. Please check and only get back to us in case something is wrong. Otherwise, please come on time… Read more Please note the exam schedule for the following days that has been posted on the Materials page. Please check and only get back to us in case something is wrong. Otherwise, please come on time but wait outside the office (E2.1, 1.14) without knocking. Thank you! 
ReexamsWritten on 06.10.23 (last change on 06.10.23) by Sven Rahmann We have now opened a scheduler for the reexams. For now, the only day is Wednesday, 18.10. If all slots fill up quickly, we can offer additional exams on Thursday 19. Please select a single(!) slot and only post a comment if there is a problem: … Read more We have now opened a scheduler for the reexams. For now, the only day is Wednesday, 18.10. If all slots fill up quickly, we can offer additional exams on Thursday 19. Please select a single(!) slot and only post a comment if there is a problem: https://terminplaner6.dfn.de/de/p/fe19b8251b1e57f745b18b7cec5ef9e3417079 Note that LSF registration is mandatory up to 1 week before the exam, and it will be available shortly. Thank you! 
Reexam periodWritten on 28.07.23 by Sven Rahmann Dear all, as it was asked today, the reexams are planned for the latest possible days before the winter lecture period; this means on one of the days 18.20.10. The lecture period starts on Monday 23.10. You can (in contrast to what was written before on this page) use this to improve your grade… Read more Dear all, as it was asked today, the reexams are planned for the latest possible days before the winter lecture period; this means on one of the days 18.20.10. The lecture period starts on Monday 23.10. You can (in contrast to what was written before on this page) use this to improve your grade from the first round if you are in your regular study time (first 4 semesters in the Master programs, first 6 semesters in the Bachelor programs). You cannot improve your grade in the next year. 
Exam Schedule PublishedWritten on 25.07.23 by Sven Rahmann Please have a look in the Materials section to view the exam schedule (first round). The exams take place in E2.1, room 1.14. Please be there on time, but do not knock. We will let you in when the previous exam is finished. 
LSF Registration ends today 23:59Written on 24.07.23 by Sven Rahmann Dear all, the possibility to (un)register for the exam on LSF ends today! No changes will be possible after midnight. 
Exam Time Slot Registration Now OpenWritten on 12.07.23 by Sven Rahmann Dear all, please register now for an exam time slot, BOTH on the planner (link in Materials) and on LSF. Please only register for a single time slot. 
Course Evaluation and Last AssignmentWritten on 06.07.23 by Sven Rahmann Dear all, please evaluate the "Algorithms for Sequence Analysis" course (separately for lecture and tutorial). The links are on top of the Materials section. Unfortunately, they are only valid until SUNDAY, so please evaluate us this week! Thank you for your time; especially your freetext feedback… Read more Dear all, please evaluate the "Algorithms for Sequence Analysis" course (separately for lecture and tutorial). The links are on top of the Materials section. Unfortunately, they are only valid until SUNDAY, so please evaluate us this week! Thank you for your time; especially your freetext feedback helps us to improve the course. On another note, we have put the last regular assignment (#11) online. There will be an optional bonus assignment (#12) next week that you can use to get a small number of missing points if necessary. (In general, bonus means: The points you receive will be counted towards your total, but the maximum possible points of these tasks are not counted for the requirements.)

Exam qualificationWritten on 03.07.23 by Jens Zentgraf Dear all, I would like to remind you of the requirements for admission to the exam. You need 50% of the points in theory AND programming. Furthermore, you must present at least one task in the tutorial. 
Exam DatesWritten on 26.06.23 by Sven Rahmann Dear all, the first exam dates for "Algorithms for Sequence Analysis" are  Friday 28.07.2023 Dear all, the first exam dates for "Algorithms for Sequence Analysis" are  Friday 28.07.2023 The second round (reexams) will be later in October (week of 913); the number of days will depend on the number of reexams. 
Tutorial: Room change on Thursday, 22.06.Written on 20.06.23 by Jens Zentgraf Dear all, the tutorial this Thursday will take place in room 1.06.

No lecture on Tuesday, 20.06.Written on 18.06.23 by Sven Rahmann Good morning, unfortunately, the lecture on Tuesday, 20.06., has to be cancelled. In the following lectures, we will discuss online and indexbased approximate pattern search algorithms, and then different versions of sequence alignment. 
Tutorials and assignment 06 programming taskWritten on 02.06.23 by Jens Zentgraf Dear all, some information regarding the tutorials of the next weeks.  06.06. and 08.06 no tutorials.  15.06: No tutorial, please join the tutorial on Tuesday (13.06). Programming task assignment 06: It seems that there was a bit of confusion regarding the programming task of… Read more Dear all, some information regarding the tutorials of the next weeks.  06.06. and 08.06 no tutorials.  15.06: No tutorial, please join the tutorial on Tuesday (13.06). Programming task assignment 06: It seems that there was a bit of confusion regarding the programming task of assignment 06. The deadline as stated on the assignment was yesterday (01.06) at 23:59. I extend the deadline until today (02.06.) 23:59. So, please submit your solutions today. Jens 
Next Lectures; Assignment 07Written on 01.06.23 by Sven Rahmann Hello everyone, a few updates about the next lectures:  No lectures next week (I am away on Tuesday, and Thursday is a holiday).  The next lecture is thus on Tue 13.06., about compression (bzip2 using the BWT, but also other compression methods).  This will end the (big) chapter 2 on… Read more Hello everyone, a few updates about the next lectures:  No lectures next week (I am away on Tuesday, and Thursday is a holiday).  The next lecture is thus on Tue 13.06., about compression (bzip2 using the BWT, but also other compression methods).  This will end the (big) chapter 2 on text indexing. We will then move on to chapter 3 on errortolerant pattern search. And about today's assignment 07:  The assignment is due in 2 weeks (15.06.), but contains roughly work for 1 week.  It will be uploaded this afternoon. Have a nice week! 
Exam DatesWritten on 23.05.23 by Sven Rahmann Hello everyone, as it was asked about several times: The final exam will be an oral exam about the lecture + exercises, but you won't have to do programming during the exam (however, you need to have understood your programming exercises, i.e. you do not need to write code, but may need to read… Read more Hello everyone, as it was asked about several times: The final exam will be an oral exam about the lecture + exercises, but you won't have to do programming during the exam (however, you need to have understood your programming exercises, i.e. you do not need to write code, but may need to read code). One of you was so kind to create a doodle about the most convenient exam dates in the first two weeks in the lecturefree period. Thank you. The link is in the forum; please vote! I will select the two best consecutive dates on which I am also available. A reexam (for all who cannot make it to the first exam or fail) will be conducted towards the end of the lecturefree period, shortly before the start of the winter semester lectures. These dates will be discussed later. 
Next LecturesWritten on 10.05.23 by Sven Rahmann Good evening, we would like to give you heads up on the next few lectures, as the schedule will be slightly irregular. Tomorrow (Thu May 11) is a regular lecture, and we will start discussing a lineartime suffix array construction algorithm (SAIS). Probably we will only discuss the easy part of… Read more Good evening, we would like to give you heads up on the next few lectures, as the schedule will be slightly irregular. Tomorrow (Thu May 11) is a regular lecture, and we will start discussing a lineartime suffix array construction algorithm (SAIS). Probably we will only discuss the easy part of the algorithm. We will also put out assignment 05 tomorrow, which is longer than usual and will last for 2 weeks. It contains one assignment (05.3) on Onotation and one assignment (05.4) on amortized analysis to give you some practice with those topics. If you are not very familiar with them, we will put some links into the Materials/Resources where you can find helpful videos about them. Then, the exercises are just logical thinking and common sense. The reason for the long assignment is that there will be a break in the lecture schedule, as I am away next Tuesday, and Thursday is a holiday (Ascension day / Father's day). So, no lectures next week! Also, no exercises, and your questions about assignment 05 should go to the forum if possible. On the Tuesday after next week, we will conclude our discussion of the SAIS algorithm and then explore further extensions of suffix arrays and related things. 
Chapter 1 CompletedWritten on 27.04.23 by Sven Rahmann Dear all, this morning, we have (already!) completed chapter 1 of the course (exact online pattern search algorithms). The slides are in the Materials section now. As always, we appreciate feedback when you find errors or omissions. Next week, we will begin the next chapter about index data… Read more Dear all, this morning, we have (already!) completed chapter 1 of the course (exact online pattern search algorithms). The slides are in the Materials section now. As always, we appreciate feedback when you find errors or omissions. Next week, we will begin the next chapter about index data structures. Please remember to submit assignment 2 by tonight. Later today, we will upload assignment 3, which will be due in 1 week. 
Welcome to the Course!Written on 14.04.23 by Sven Rahmann Hello everyone, the first week is already over, and in the first lecture on Thursday, we discussed administrative business, basic definitions, the exact pattern search (or pattern matching) problem, and analysed the naive algorithm, both in a worstcase and in an averagecase sense, with perhaps an… Read more Hello everyone, the first week is already over, and in the first lecture on Thursday, we discussed administrative business, basic definitions, the exact pattern search (or pattern matching) problem, and analysed the naive algorithm, both in a worstcase and in an averagecase sense, with perhaps an unexpected result. Over the next week, we will discuss various better algorithmic approaches than the naive one. A first assignment sheet has been uploaded; it is due on Thursday (20.04.)! Please indicate your tutorial preferences as soon as possible; we want to make the tutorial assignment on Monday, so you can go to your assigned tutorial on Tuesday or Thursday if you have any questions next week. In the meantime, questions can be asked in our forum. We have also posted a link to the 2022 lecture videos in the Materials; perhaps in can be helpful. However, the 2023 exam will be about the 2023 lectures, and small content differences will occur, especially towards the end of the term! 
Algorithms for Sequence Analysis
(Special lecture 4V+2Ü, 9 CP for MSc Bioinformatics, open to other CS degree programs as well: Computer Science, DSAI, Cybersecurity, etc.)
The lectures start on Thursday April 13, 2023. The last lecture is on Thursday, July 20, 2022 (summary and review).
Lecture Dates:
 Every Tuesday 08:30  10:00 (not on April 11; this is the semester kickoff day!)
 Every Thursday 08:30  10:00
 except on official holidays (Ascension Day, Corpus Christi, etc.)
 Room: E2.1, room 0.01 (Center for Bioinformatics, seminar room, ground floor)
Tutorials:
 Every Tuesday (14:15  15:45, E2 1 room 001)
 Every Thursday (14:15  15:45, E2 1 room 001)
You need to be registered for this course in order to access the Materials section with lecture slides, homework assignments, etc.
Contents
Some of the topics discussed are
 different algorithms for exact pattern search (searching for substrings in longer strings)
 data structures for fulltext indexing, in particular suffix tree, array, BurrowsWheeler transform, FM index
 useful companion data structures: rank (and select) data structures on bit sequences; wavelet trees
 applications of fulltext indexes in genomics (repeat finding, etc.)
 errortolerant pattern search in strings (Hamming distance; edit distance)
 biological sequence alignment and models of evolutionary processes
 algorithm engineering for sequence alignment (affine gap costs; linear space; different objectives)
 the read mapping problem; seedfilterextend approaches
 text compression algorithms
 alignmentfree sequence analysis: basics, methods, successes, challenges
Requirements
The are no special requirements for the course. However, you should be familiar with elementary algorithms and data structures (sorting; stacks, queues) and algorithm analysis (asymptotic notation like O(n)). For bioinformatics, this is a fairly theoretical and formal course about algorithms. For theoretical computer scientists, this is a fairly practical course, actually considering good implementations of different algorithms. Programming skills are absolutely necessary to solve the practical homework exercises. Do not take this course if you have no or poor programming skills; it will not work out well.
Passing the Course
In order to pass this (graded) course for 9 ECTS credits, a number of conditions needs to be satisfied:
 You need to register for the course here in the CMS to access the course materials, including homework.
 You need to achieve at least 50% of all possible points in the homework, in both the theoretical exercises and in the programming exercises (of which there are some, but fewer than theoretical exercises). (Yes, this means at least 50% in each category separately. If you cannot program, do not take this course!)
 You need to attend a tutorial regularly and present some of your homework solutions. The tutors will keep track of when you do this.
 When you qualify for the exam, you need to register for it in the LSF system (instructions will come towards the end of the semester; exam dates will be shortly after the lecture period). LSF registration closes one week before the exam; no exceptions.
 The exam will check your understanding of a broad variety of topics taught in the course and from the homework. Usually the exam is an oral exam; it will only be a written exam if the number of qualifying course participants is above 20. This will be estimated and announced within April.
ReAdmission in the Next Exam Period
If you qualified for the exam in one exam period (say, summer '22), but then failed the exam(s), and you want to retake the exam one year later (say, summer '23), then you have to requalify (i.e., do the homework again and obtain enough points). Only in very rare individual circumstances, this requirement might be waived. If you need to discuss such circumstances, please do it very early in the semester. No exceptions will be made shortly before the examination week. in any case, it is highly recommended to prepare for the exam by solving the homework assignments!