News
|
02.06.2023
|
Tutorials and assignment 06 programming taskDear 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... 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 |
|
01.06.2023
|
Next Lectures; Assignment 07Hello 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). -... 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 error-tolerant 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! |
|
23.05.2023
|
Exam DatesHello 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... 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 lecture-free 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 re-exam (for all who cannot make it to the first exam or fail) will be conducted towards the end of the lecture-free period, shortly before the start of the winter semester lectures. These dates will be discussed later. |
|
10.05.2023
|
Next LecturesGood 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 linear-time suffix array construction algorithm (SAIS). Probably... 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 linear-time 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 O-notation 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. |
|
27.04.2023
|
Chapter 1 CompletedDear 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... 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. |
|
14.04.2023
|
Welcome to the Course!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 worst-case and in 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 worst-case and in an average-case 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 kick-off 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 full-text indexing, in particular suffix tree, array, Burrows-Wheeler transform, FM index
- useful companion data structures: rank (and select) data structures on bit sequences; wavelet trees
- applications of full-text indexes in genomics (repeat finding, etc.)
- error-tolerant 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; seed-filter-extend approaches
- text compression algorithms
- alignment-free 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.
Grade Improvement
Please note that grade improvement (taking the exam again after passing it once) is not(!) possible with this course, not even in the same examination period. This is described in the Bioinformatics-specific study regulations.
Re-Admission 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 re-take the exam one year later (say, summer '23), then you have to re-qualify (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!