Note: This page will be updated every week as the course progresses.
Here you can get back to the main page of the course.
News:
Projects:
Note: This schedule is supposed to give information about what we covered. You still need the notes from the lecture; if you cannot attend, please get in touch with someone who does. Here I try to give the corresponding chapters in the two books Setubal & Meidanis (S&M) and Jones & Pevzner (J&P); for more books, see the main page of the course.
There are very nice lecture notes on Sequence Analysis by Jens Stoye and others from Bielefeld University. They are much too detailed for our purposes, but I do use some chapters. I refer to them below by BielefeldSeqAnLN.
I twice gave a one-week intensive course on algorithms for biology masters students at the University of the Western Cape, Cape Town, South Africa. The CT course notes are short and easy to understand. All of it is useful for you except the part on exact matching (sec. 3.3 to 3.6). (But if you are interested, read that part, too. Everything is explained in a simple and straightforward manner.)
For the phylogenetics part, I use mostly the Bielefeld Phylogenetics Lecture Notes: BielefeldPhyloLN.
No. | Date | Topic | Chapters | Other materials (supporting material, suggested reading) |
---|---|---|---|---|
1+2 | Mo+Wed, 4+6/3/2013 | Organisation of course; Pairwise sequence alignment 1: definition of alignment, exhaustive search, DP algorithm of Needleman-Wunsch; Formalism on strings |
S&M 3.1, 3.2.1; J&P 6.4, 6.6 | Section 3.1 of the CT course notes (formalism on strings). Section 2.4 of the BielefeldSeqAnLN. |
3 | Mo, 11/3/2013 | Basic combinatorics, counting strings, counting alignments | Section 5 of the CT course notes (basic combinatorics); Sections 2.4 and 5.2 of the BielefeldSeqAnLN. | |
4 | Wed, 13/3/2013 | Pairwise sequence alignment 2: Analysis of DP-algo for global alignment, Local alignment (Smith-Waterman) | S&M 3.2.2, J&P 6.8 | |
5 | Mo, 18/3/2013 | Introduction to algorithm analysis, Big-Oh notation | S&M 2.3, J&P 2.8 | Section 4 (except 4.3) of the CT course notes. Section 2 could also be useful for non-computer scientists (a very basic explanation of algorithms). Here is also the "dirty trick version" of how to identify O-classes. Section 2.3 of the BielefeldSeqAnLN. |
6 | Wed, 20/3/2013 | Pairwise sequence alignment 3: Analysis of local alignment algorithm; other variants: saving space for global alignment, semiglobal alignment, general and affine gap functions (sketch) | S&M 3.2.3, 3.3.1-3.3.3, J&P 6.9 | Section 5.5 of the BielefeldSeqAnLN. |
7 | Mo, 25/3/2013 | Multiple Sequence Alignment 1: sum-of-pairs-score, DP algorithm | S&M 3.4.1, J&P 6.10 | Chapter 13 of the BielefeldSeqAnLN (parts only). |
8 | Wed, 27/3/2013 | Multiple Sequence Alignment 2: Heuristics. Star alignment, Progressive alignment |
S&M 3.4.2 | Chapter 16 of the BielefeldSeqAnLN (parts only). |
9 | Wed, 3/4/2013 | Multiple Sequence Alignment 3: Progressive alignment analysis; advantages and disadvantages; Scoring matrices 1: introduction |
S&M 3.5.1 | |
10 | Mon, 8/4/2013 | Scoring matrices 2: PAM-matrices; BLOSUM matrices (sketch) |
S&M 3.5.1, J&P 6.7 | Here are two PAM mutation matrices, and two PAM scoring matrices (the ones handed out in the lecture). Here is a nice set of slides by David Gilbert, Univ. of Glasgow, on scoring matrices. You can also read the original article on PAM matrices (more exactly, book chapter), by Margret Dayhoff et al, 1978. It is very understandable! See also this nice little article by Sean Eddy about the BLOSUM matrices (S. Eddy, Where did the BLOSUM62 alignment score matrix come from?, Nature Biotechnology 22, pp. 1035-1036, 2004). |
11 | Mon, 15/4/2013 | Heuristic database search 1: dotplots, FASTA | S&M 3.5.3, J&P 9.8 | Chapter 6 (in part. 6.1, 6.4.1) of the BielefeldSeqAnLN. There are some nice dotplots, with good explanation, in the book by Mount, see here. See also the original article on FASTA. |
12 | Wed, 17/4/2013 | Summary of part 1 | additional office hours: Wed 17/4 14.30-15.30, Thu 18/4 10-12 | |
13 | Mon, 22/4/2013 | Introduction of projects | Here are the project descriptions. | |
14 | Wed, 24/4/2013 | Midterm exam | Aula D, 8.45-11.15. Here is a list of things you should know for the exam. Here are the results. | |
15 | Mon, 29/4/2013 | Heuristic database search 2: BLAST | S&M 3.5.2, J&P 9.8 | Section 6.4.2 of the BielefeldSeqAnLN. Here is the orginal article on BLAST: S.F. Altschul et al. Basic Local Alignment Search Tool, J. Mol. Biol. 215: 403-410 (1990). |
16 | Mon, 6/5/2013 | Discussion of midterm exam; Introduction to phylogenetics 1: History of systematics | ||
17 | Wed, 8/5/2013 | Introduction to phylogenetics (cont'ed): different types of phylogenetic trees, different types of input | BielefeldPhyloLN, ch. 1, 2.3 | |
18 | Mon, 13/5/2013 | Little introduction to graphs and trees, number of phylogenetic trees | BielefeldPhyloLN, ch. 2; | |
19 | Wed, 15/5/2013 | Distance based methods: UPGMA | S&M 6.5, J&P 10.6,10.8 | BielefeldPhylo, ch. 6.1 and 6.2, Durbin-book ch. 7.3, Felsenstein-book ch. 11 (pp. 161-166). |
20 | Mon, 20/5/2013 | Distance based methods (cont'ed): UPGMA analysis, ultrametrics; Character-based methods: Perfect Phylogeny | S&M 6.1, J&P 10.9 | BielefeldPhyloLN ch. 3.1, 3.2. |
21 | Wed, 22/5/2013 (4 hours) | Character based methods cont'ed: Small Parsimony, Fitch' algorithm. Large Parsimony: exhaustive search, Nearest Neighbor Interchange (NNI). | S&M 6.4, J&P 10.10, 10.11 | Durbin-book ch. 7.4., Felsenstein-book, ch. 4, BielefeldPhyloLN, ch. 4.1, 4.2, 5.1,5.2; (If you want to read about NP-completeness, here is a chapter I once wrote: Chapter on NP-completeness. It is not part of this course! NP-completeness is out of scope of this course. This is only for whoever is interested.) |
22 | Mon, 27/5/2013 (4 hours) | Large and small parsimony example: NNI and Fitch' applied. Summary of Part II. Question time. | Felsenstein book, ch. 4. | |
-- | Wed, 29/5/2013 | Project presentations (full program see here). | ||
23 | Mon, 3/6/2013 | Final written exam. | Aula B, 9.00-11.30 (short version) or 9.00-12.30 (long version). Here is a list of things you should know for the exam. Exam results of 3/6/2013 here. | |
-- | Tue, 4/6/2013 | Project presentations (full program see here). | ||
-- | Thu, 6/6/2013 | Project presentations (full program see here). |