Molecular Sequence Algorithms (Spring 2004) Course Home page

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

• Molecular Sequence 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 (string algorithms) that lay the foundation for, and are applicable to the exploitation of molecular sequence data (DNA, RNA, and protein).

Announcements

• Mar 3, 2004: A course feedback form is available here. Please return a filled copy of the form either at the last exercise session, or to my mail box, or to fhe feedback mail box in the first-floor corridor.
• Feb 29, 2004: The final exam is arranged as a home exam to be returned by Monday, March 15. The instructions and assignments are available online.
• Jan 15, 2004: More international students have joined the course, and therefore we'll continue to have lectures and exercise sessions in English.
• Dec 19, 2003: This is a preliminary version of the course home page. Please monitor this page for updates.

Practical arrangements

The course consists of ...

• 16 * 2 hours of lectures (January 14 - March 3, 2004).

The first lecture takes place on Wednesday 14, 2004, at 8.15-10 in class E16-E17. (Changes are possible: Please check the on-line schedules for possible updates.)

A preliminary course syllabus is available here.

Language of instruction: If there is sufficient demand, the course will be given in English; say, if that is requested by more than one non-Finnish speaker actively participating in the course. Please contact the lecturer in advance 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 (January 27 - March 8)

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

• Final exam is arranged as a home exam. The solutions shall be returned by Monday, March 15, 2004, at noon. The re-take exam will be a typical in-class exam on Monday, April 5, 2004, at 14-18 in E26/27.

Grading: The grade is determined by the formula

 
    ceiling(12*Exam + 4*Exerc - 4) ,

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 ceiling(x) means rounding up to the closest integer that is at least x.) The re-take exam can be graded either based on this formula or on exam points only, which ever gives the better result. In any case, at least half of the exam points are required to pass the course. The lowest accepted grade is 3.

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!

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 14) [Full-size PDF slides] * [Reduced PDF for printing]
2. Naive string matching and fundamental preprocessing (January 15) [Full-size PDF slides] * [Reduced PDF for printing]
3. Boyer-Moore matching (January 19) [Full-size PDF slides] * [Reduced PDF for printing] (with small corrections on Jan 19)
4. Exact set matching and Aho-Corasick method (January 21) [Full-size PDF slides] * [Reduced PDF for printing] * [Reduced PS for printing]
5. The Shift-And Method (January 26) [Full-size PDF slides] * [Reduced PDF for printing] (with small corrections on Jan 28)
6. Introduction to Suffix Trees (January 28) [Full-size PDF slides] * [Reduced PDF for printing]
7. Linear-time Construction of Suffix Trees (February 2 and 4) [Full-size PDF slides] * [Reduced PDF for printing]
8. Applications of Suffix Trees (February 9 and 11) [Full-size PDF slides] * [Reduced PDF for printing]
9. Core String Edits and Alignments (February 16) [Full-size PDF slides] * [Reduced PDF for printing]
10. Local Alignments and Gaps (February 18 and 23) [Full-size PDF slides] * [Reduced PDF for printing]
11. Introduction to Multiple Alignments (February 23) [Full-size PDF slides] * [Reduced PDF for printing]
12. Computing Multiple Alignments (February 25 and March 1) [Full-size PDF slides] * [Reduced PDF for printing]
13. Sequence Database Searching (March 1 and 3) [Full-size PDF slides]
    • [Reduced PDF for printing] Part 1
    • [Reduced PDF for printing] Part 2

Exercise assignments

Homework assignments for the exercise sessions will be posted here:

Session 1 (January 27)
Session 2 (February 2)
Session 3 (February 9)
Session 4 (February 16)
Session 5 (February 23)
Session 6 (March 1)
Session 7 (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, and 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

Only three students returned the course feedback form. A summary of their feedback is found here.