ign AiBS Q1/2007 - Schedule

Algorithms in Bioinformatics - Q1
AiBS Q1/2007
DAIMI / Courses/ AiBS / Schedule

Weekly Schedule

Lectures take place:

  • Tuesdays 08.15-09.00, Shannon-157.
  • Fridays 13.15-15.00, Shannon-157.

The topic of each lecture and reading material will be listed below.

Week 1 Tue, Aug 28

Introduction to the course. Biological sequences DNA, RNA and proteins. Global pairwise alignment with linear gapcost.

Reading material:
  • About biological sequences: J. Setubal and J. Meidanis. Basic Concepts of Molecular Biology. Sections 1.1-1.4 of Introduction of Computational Molecular Biology, Brooks/Cole Publishing Company, 1997.
  • About global pairwise alignment: Sections 10, 11.1-11.6 and 11.8 in D. Gusfield. Core String Edits, Alignments, and Dynamic Programming. Section 10 and 11 of Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.

    The Bibliography and Glossary from Gusfield's book might also be useful.

Additional material: Slides from lecture:
Fri, Aug 31

Global alignment with general and affine gapcost. Local alignment (a simple but powerful extension of the basic global alignment algorithm).

Reading material:

  • About general and affine gapcost: Section 11.8 in D. Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997. Available in hand out from last time.
  • About local alignment: Section 11.7 in D. Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997. Available in hand out from last time.
Additional material: Slides from lecture:
Week 2 Tue, Sep 4

Finding an optimal (global) alignment with linear (and affine) gapcost in linear space (Hirschberg's algorithm). We will focus on the technique presented by Durbin et al.

Reading material:

  • About linear space alignment: Section 12.1 in in D. Gusfield. Refining Core String Edits and Alignments. Parts of section 12 of Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
  • About linear space alignment: R. Durbin, S. Eddy, A. Krogh and G. Mitchison. Linear space alignments. Section 2.6 of Biological Sequence Analysis: Probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998. (another way to implement "Hirschbergs trick" for saving space)
Additional material: Slides from lecture:
Fri, Sep 7

Introduction to the first mandatory project about sequence comparison. (There will only be a lecture from 13:15-14:00).

Week 3 Tue, Sep 11

No lecture. Use the time to work on the mandatory project.

Fri, Sep 14

Speeding up the computation of global alignment (the special case of unit cost edit distance) using the "four Russian trick". (The lecture is given by Søren Besenbacher).

Reading material:

  • About speeding up the computation of unit cost edit distance: D. Gusfield. The Four-Russians speedup. Section 12.7 of Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
Slides from lecture:
Week 4 Tue, Sep 18

Multiple alignment. Computing an optimal multiple alignment using SP- and tree-score.

Reading material:

  • About multiple alignment: Sections 14.1-14.2 and 14.5-14.10 in D. Gusfield. Multiple String Comparison - The Holy Grail. Chapter 14 of Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997. Don't spend too much time geeting into the details of sections 14.7-14.10. We will look at 14.6.2 in details on Friday.
Slides from lecture:
Fri, Sep 21

A approximation algorithm for multiple alignment using SP-score. Reading material:

Slides from lecture:
Week 5 Tue, Sep 25

Hand in and discussion of the 1st mandatory project, e.g. how to obtain an optimal pairwise global alignment using affine gap cost in linear space.

Fri, Sep 28

Hidden Markov models (HMMs) and applications in bioinformatics as sequence profiles and pair HMMs. Introduction to 2nd mandatory project.

Reading material:

  • R. Durbin, S. Eddy, A. Krogh and G. Mitchison. Markov chains and hidden Markov models. Section 3.0-3.3 of Biological Sequence Analysis: Probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.
  • R. Durbin, S. Eddy, A. Krogh and G. Mitchison. Pair HMMs. Section 4.1 of Biological Sequence Analysis: Probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.
  • Christian N. S. Pedersen. Multiple Sequence Comparison and HMMs. Pages 23-30 from BRICS DS-00-04 C.N.S. Pedersen: Algorithms in Computational Biology.
Additional material: Slides from lecture:
Week 6 Tue, Oct 2

Gene prediction. Problem definition and gene prediction in a single sequence.

Reading material:

  • N. C. Jones and P. A. Pevzner. Gene Prediction. Sections 6.11-6.14 of An introduction to bioinformatics algorithms, MIT Press, 2004.
  • S. L. Salzberg. Gene Discovery in DNA Sequences. IEEE Intelligent Systems, pages 44-48, Nov/Dec 1999.
Addition material: Slides from lecture:
Fri, Oct 5

Gene prediction, continued. Pairwise gene prediction.

Reading material:

Slides from lecture:
Week 7 Tue, Oct 9

Progressive multiple alignment.

Reading material:

  • Section 14.10 (until 14.10.3) in D. Gusfield. Multiple String Comparison - The Holy Grail. Chapter 14 of Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
Addition material:
Fri, Oct 12

Alignment of whole genomes. Discussion of exam question (if any questions). Presentation of possible thesis projects.

Reading material:

Addition material: Slides from lecture:

Last modified: Wed Nov 7 13:38:15 2007