News

No Lecture on Thursday, 23.05.

Written on 21.05.24 by Sven Rahmann

Dear all, there will be not lecture on Thursday 23.05. due to my absence from Saarbrücken. Enjoy the free time. Next week, we discuss the Burrows-Wheeler transformation.

Cases of Plagiarism

Written on 01.05.24 by Sven Rahmann

It has come to our attention that some of you have tried to copy solutions. This is plagiarism. (Solutions were actually wrong, too.) Plagiarism will be punished to the maximum extent. It is unethical and has no place in academia. This is what will happen:

1. You will be kicked out of the… Read more

It has come to our attention that some of you have tried to copy solutions. This is plagiarism. (Solutions were actually wrong, too.) Plagiarism will be punished to the maximum extent. It is unethical and has no place in academia. This is what will happen:

1. You will be kicked out of the course.

2. You will be reported to the examination board.

3. In case of a repeated report to the examination board, they can remove you from the study program.

This is not a joke.  Before you think of copying (from someone else, from the internet, from ChatGPT, wherever), think again. If you find the assignments hard, come to the tutorials where the tutor can explain things. If you don't have enough time, don't take the course. Copying is not a solution, it's a problem, and if you do it, it can destroy your academic career entirely.

 

Assignment 01

Written on 26.04.24 by Jens Zentgraf

Dear all,

there was an error on task 4 in assignment 01. 

If you use more than one character, you cannot skip the last characters in the pattern. 
For P=BAAAAB and l=2 we would skip AB and if we see AB in the text we would do a shift of the pattern length 6.

BAAAAB
BAAAABAAAABAAA    shift… Read more

Dear all,

there was an error on task 4 in assignment 01. 

If you use more than one character, you cannot skip the last characters in the pattern. 
For P=BAAAAB and l=2 we would skip AB and if we see AB in the text we would do a shift of the pattern length 6.

BAAAAB
BAAAABAAAABAAA    shift based on AB 

      BAAAAB
BAAAABAAAABAAA    We miss the second hit.

To deal with this, you have to check if a part of the suffix (of length l) of the pattern is a prefix of the pattern. (Does the end overlap the start of the pattern). Then you have to adapt the shift for all suffixes for which this is the case.

I uploaded a new assignment in which you can find the shifts for P=BAAAAB for l=1,2,3.

If you have questions, do not hesitate to ask in the forum.

Best 
Jens
 

Assignment 00

Written on 22.04.24 by Jens Zentgraf

Dear all,

the deadline for assignment 00 is approaching (today 22.04. 23:59).
Please make sure that you upload your solution to the cms.

If you solve the task in python, please upload the python file.
If you solve the assignment in another language, please upload all necessary files and… Read more

Dear all,

the deadline for assignment 00 is approaching (today 22.04. 23:59).
Please make sure that you upload your solution to the cms.

If you solve the task in python, please upload the python file.
If you solve the assignment in another language, please upload all necessary files and provide a short explanation how to (compile and) execute the code.

Best
Jens
 

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 Tuesday April 16, 2024. The last lecture is on Thursday, July 25, 2024 (summary and review).

Lecture Dates:

  • every Tuesday 08:30 - 10:00
  • every Thursday 08:30 - 10:00
  • except on official holidays
  • Room: E2.1, room 0.01 (Center for Bioinformatics, seminar room, ground floor)

Tutorials:

  • every Wednesday (10:15 - 11:45, E2.1 room 001)
  • every Thursday (10:15 - 11: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 15 or above. This will be estimated and announced within the month of April.

No Grade Improvement

Important: Once you have passed the exam, you cannot re-take it to improve your grade. This is different from basic lectures where there is an improvement possibility within the same exam period. 

No Automatic Re-Admission for the Next Exam Period

If you qualified for the exam in one exam period (say, summer '24), but then failed the exam(s), and you want to re-take the exam one year later (say, summer '25), then you have to re-qualify (i.e., do the homework again and obtain enough points). In any case, it is highly recommended to prepare for the exam by solving the homework assignments!

Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.