CSMACMB - Algorithms for Computational Molecular Biology

January-March 2007

Lecturer

Maxime Crochemore
Exercises by Guillaume Blin

Aims

The aims of the course are: (i) to understand the major concepts and problems of computational molecular biology; (ii) to appreciate the importance of these concepts in a wide diversity of practical applications; (iii) to learn which of the computational molecular biology problems have efficient algorithmic solutions and which are intractable; (iv) for some intractable problems, to understand how heuristic approaches to problem solution may yield fast but only approximate solutions.

Syllabus

Lectures include the following topics:

1. Introduction to Molecular Biology and Genomics
2. Pairwise Sequence Alignment
3. Substitution Matrices and Alignment Statistics
4. Sequence Searching
5. Multiple Sequence Alignment [SM pp. 69--80]
6. Whole Genome Alignment [Maximal repeats]
7. Genome rearrangements
8. Phylogenies [SM pp. 177--185]
9. Inferring Phylogenetic Trees
10. Fragment assembly of DNA
11. RNA Structure Prediction [SM pp. 245--252]

Related textbooks

[Gu] D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, New York, 1997, 534 pages.
[SM] J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, PWS Publishing Co., 1997, 296 pages.

Other books

M. Crochemore, C. Hancart et T. Lecroq, Algorithmique du texte, Vuibert, Paris, 2001, 347 pages.
R. Durbin, S. Eddy, A. Krogh, G. Mitchison, Biological sequence analysis, Cambridge University Press, 1998, 356 pages.
P. A. Pevzner, Computational Molecular Biology, The MIT Press, 2000, 314 pages.
M.S. Waterman, Introduction to Computational Biology, Chapman & Hall, 1995, 431 pages.