Biosequence Algorithms (Spring 2007) Home Page

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

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

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

Announcements

• Apr 27, 2007: A summary of course feedback is available. The retake exam of April 20 has been marked: one fail, and one pass with a satisfactory grade. You can check the marking in the department office.
• Apr 2, 2007: The final exam of March 23 has been marked. Two failed, while three passed the course with grades good - very good based on exam answers and exercise activity. You can check the marking in the department office. (Currently closed; please contact Leila Tiihonen in D2034 if you want to check your marking before the Easter.)
• Mar 8, 2007: The course feedback form is available. Please fill and return it at the last exercise session to get a bonus exercise point.
• Febr 15, 2007: The exercise session of Thursday, February 22 has been moved to Friday, February 23, at 12.15 - 14 in class E14-15.
• Febr 9, 2007: The lecture of Wednesday, February 14 has been moved to Thursday, February 15, at 10-12 in class MT6.
• Jan 18, 2007: This is a preliminary version of the course home page. Please monitor this page for announcements, lecture notes and assignments.

Practical arrangements

Please register on the course through Wossikka. (Registration is possible at the lecture, too, but without using Wossikka you may fail to be included in the course mailing list.)

The course consists of ...

• 16 * 2 hours of lectures (January 22 - March 14, 2007).

The first lecture takes place on January 22, 2007, at 10.15-12 in class MT2. (Please check the on-line schedules for possible updates.) The lectures are given by Pekka Kilpeläinen.

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. For communication, either English of Finnish can be used.

• 7 * 2 hours of exercise sessions (January 30 - March 16)

The exercise sessions are chaired by Liisa Heikkinen.

• Final exam on Friday, March 23 at 8-12 in class L2.
• Re-take exam on Friday, April 20, 2007, at 12-16 in class L21.

Grading: The grade is determined by the formula

    round(6*Exam+ 2*Exerc -2.5) ,

where Exam is the fraction of obtained exam points out of the maximum, and Exerc is the fraction of solved exercise assignments out of the total. The lowest accepted grade is 1, and the highest grade is 5. A minimum of 50 % of exam points is required for passing the course. Examples of grades given by the formula are available here.

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 not written especially for self-study. The idea is that the often concise formulations are explained and expanded upon at the lecture. If you cannot attend the lectures, you should try to compensate it by studying the textbook on your own.

1. Introduction (January 22)
   [Full-size PDF slides] * [Reduced PDF for printing]
2. Naive string matching and fundamental preprocessing (January 24)
   [Full-size PDF slides] * [Reduced PDF for printing]
3. Boyer-Moore Matching (January 29)
   [Full-size PDF slides] * [Reduced PDF for printing]
4. Exact set matching and Aho-Corasick method (January 31)
   [Full-size PDF slides] * [Reduced PDF for printing]
5. The Shift-And Method (February 5)
   [Full-size PDF slides] * [Reduced PDF for printing]
6. Suffix Trees: Introduction and Construction (Febr 7 and 12)
   [Full-size PDF slides] * [Reduced PDF for printing]
7. Applications of Suffix Trees (February 16 and 19)
   [Full-size PDF slides] * [Reduced PDF for printing]
8. String Edits and Alignments (February 21 and 27)
   [Full-size PDF slides] * [Reduced PDF for printing]
9. Approximate Matching, Local Alignments, and Gaps (February 27 and 28)
   [Full-size PDF slides] * [Reduced PDF for printing]
10. Multiple String Alignments (March 5 and 7)
    [Full-size PDF slides] * [Reduced PDF for printing]
11. Sequence Database Searching (March 12)
    [Full-size PDF slides] * [Reduced PDF for printing]
12. Review of the Course (March 14)

Exercise assignments

Homework assignments for the exercise sessions will be posted here:

Session 1 (January 30)
Session 2 (February 8)
Session 3 (February 13)
Session 4 (February 23) (NB the changed date and place)
Session 5 (March 1)
Session 6 (March 7)
Session 7 (March 16)

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 Data Structures and Algorithms could be considered minimum required background, and a course on Design and Analysis of Algorithms is highly recommended.

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. The course Johdatus bioinformatiikan algoritmeihin is probably useful background knowledge of algorithmic bioinformatics in general, but it is not required or assumed as a background.

Course feedback

A summary of student feedback is available here. (The feedback form can be found here.)

Summaries of student feedback form previous offerings of the course are available here:

• BSA 2004
• BSA 2005