Biosequence Algorithms (Spring 2005) Home Page

Biosekvenssien käsittelyalgoritmit (kevät 2005) -kurssin kotisivu

• Tietojenkäsittelytieteen syventävien opintojen (III-V vuosi) kurssi (3 ov)
• Biosequence Algorithms is an elective graduate level (laudatur) course (3 cu) in Computer Science.

Goals of the course: To get familiar with the fundamental algorithmic ideas and methods, that is, string algorithms that lay the foundation for, and are applicable to the exploitation of molecular sequence data (DNA, RNA, and protein).

Announcements

• Apr 19, 2005: The home exam has been marked. All who returned the home exam passed the course, with grades in the range 3 - 10, based on exercise activity and home exam answers. You can visit the department office to check the marking of your solutions.
• Mar 16, 2005: The course feedback form is available. Please fill and return it, for example at the last exercise session, to get a bonus exercise point.
• Mar 15, 2005: Exercise session 6, originally scheduled for March 8, will be held on March 21 at 14.15-16 in MT2
• Mar 7, 2005: The questions and instructions for the home exam, due to Wednesday, March 23, are available.
• Jan 20, 2005: This is a preliminary version of the course home page. Please monitor this page for announcements, lecture notes and assignments.

Practical arrangements

The course consists of ...

• 16 * 2 hours of lectures (January 25 - March 17, 2005).

The first lecture takes place on Tuesday 25, 2005, at 10.15-12 in class MT2. (Please check the on-line schedules for possible updates.)

A preliminary course syllabus is available here.

Language of instruction: If there is sufficient demand (say, by at least two active participants) the course will be given in English. Please contact the lecturer if you would like the course to be given in English. Otherwise the course will be given in Finnish. (For communication, either English of Finnish can be used.)

• 7 * 2 hours of exercise sessions (February 8 - March 21)

The lectures and the exercises are given by professor Pekka Kilpeläinen.

• The final exam will be arranged as a home exam, which is tentatively due to Wednesday, March 23, 2005, at noon.
• The re-take exam will be a typical in-class exam on Friday, April 29, 2005, at 12-16 in Microteknia Auditorium.

Grading: The grade is determined by the formula

    floor(12*Exam+ 4*Exerc -3) ,

where Exam is the fraction of given exam points out of the maximum, and Exerc is the fraction of solved exercise assignments out of the total. (Function floor(x) means truncating down to the closest integer.) The lowest accepted grade is 3, and the highest grade is 12. A minimum of 50 % of exam points is required for passing the course.

Please notice that exercise activity forms 25 % of the grade. Actively solving homework assignments is central for learning to understand and to apply the techniques; Often the process of working on the assignments is much more important than the actual "solutions" that are discussed at the exercise sessions!

The exercise points can be taken into account for the first retake exam, too, if that yields a better result, but not for the later retake exams.

Material

Copies of lecture slides and exercise assignments will be made available online.

The course is based on the textbook Algorithms on Strings, Trees, and Sequences: computer science and computational biology by Dan Gusfield (Cambridge University Press, 1999). A pair of copies are available for short-term loans in the department library.

Lecture notes

I try to deliver copies of slides here prior to the lectures. Please note that the slides are skeletons of lectures, that is, they are not written especially for self-study. If you cannot attend the lectures, you should be able to compensate it by studying the textbook on your own.

1. Introduction (January 25)
   [Full-size PDF slides] * [Reduced PDF for printing]
2. Naive string matching and fundamental preprocessing (January 28)
   [Full-size PDF slides] * [Reduced PDF for printing]
3. Boyer-Moore Matching (February 1)
   [Full-size PDF slides] * [Reduced PDF for printing]
4. Exact set matching and Aho-Corasick method (February 4)
   [Full-size PDF slides] * [Reduced PDF for printing]
5. The Shift-And Method (February 8)
   [Full-size PDF slides] * [Reduced PDF for printing]
6. Introduction to Suffix Trees (February 11)
   [Full-size PDF slides] * [Reduced PDF for printing]
7. Linear-Time Construction of Suffix Trees (February 11/15)
   [Full-size PDF slides] * [Reduced PDF for printing]
8. Applications of Suffix Trees (February 16 and 22)
   [Full-size PDF slides] * [Reduced PDF for printing]
9. String Edits and Alignments (February 23, March 2)
   [Full-size PDF slides] * [Reduced PDF for printing]
10. Approximate Matching, Local Alignments, and Gaps (March 2 and 16)
    [Full-size PDF slides] * [Reduced PDF for printing]
11. Introduction to Multiple Alignments (March 16/17)
    [Full-size PDF slides] * [Reduced PDF for printing]
12. Computing Multiple Alignments (March 17)
    [Full-size PDF slides] * [Reduced PDF for printing]

Exercise assignments

Homework assignments for the exercise sessions:

Session 1 (February 1)
Session 2 (February 8)
Session 3 (February 15)
Session 4 (February 22)
Session 5 (March 2)
Session 6 (March 21 at 14.15-16 in MT2; moved from March 8)

Assumed background

• Sufficient familiarity with algorithmics

We'll be extensively involved with basic techniques of algorithm analysis and dynamic programming; the necessary concepts will be reviewed, but familiarity with those topics will certainly be useful. A course on Design and Analysis of Algorithms is recommended. A course on Data Structures and Algorithms could be considered minimum required background.

Knowledge of molecular biology is useful for appreciating the context and motivation of the methods studied on the course, but it is not necessary for understanding the algorithmic issues that form the focus of the course.

Course feedback

The course feedback form is available here. Please fill and return it - this will give you a bonus exercise point.

A summary of student feedback is available here. Thanks for all who returned the form.