Here you can get back to the main page of the course.
Note: This schedule contains information about what we covered in each lecture. 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 books Setubal & Meidanis (S&M) and Jones & Pevzner (J&P) for the bioinoformatics, and Aczel & Sounderpandian (Aczel&S) and Bramanti (Bram) for the statistics part; for details of these and of more books, see the main page of the course.
BielefeldSeqAnLN: These 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. Below I give the exact chapters where you can find what we covered, if applicable.
CT course notes: 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. These lecture 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, and 4.3). (But if you are interested, you can read that part, too. It explains and analyses in detail a different algorithm for a different problem. Everything is explained in a simple and straightforward manner. However, that part will not be needed for this course.)
BielefeldPhyloLN: For the phylogenetics part, I use mostly these lecture notes on Phylogenetics from the University of Bielefeld, by Jens Stoye and others.
| No. | Date | Topic | Chapters in books | Other materials (supporting material, suggested reading) | |
|---|---|---|---|---|---|
| 1 | Wed, 5/3/2014 (2h) | Organisation of course (slides); computational efficiency I (Fibonacci numbers) (slides) | J&P 2.6 (p.31 onwards), 2.7 | Section 2 of the CT course notes (What is an algorithm?); slides on Fibonacci numbers | |
| 2 | Wed, 12/3/2014 (3h) | Pairwise sequence alignment 1: motivation/applications, informal introduction, scoring alignments, exhaustive search; formalism on strings | S&M 3.1; J&P 2.9.1 | Section 3.1 of the CT course notes (formalism on strings). Section 2.4 of the BielefeldSeqAnLN. | |
| 3 | Fri, 14/3/2014 (2h) | Formal definition of global alignment problem, DP algorithm of Needleman-Wunsch | S&M 3.2.1; J&P 2.9.4, 6.6 | ||
| 4 | Wed, 19/3/2014 (3h) | Analysis of DP algorithm for global alignment; some string combinatorics; number of alignments | S&M 3.2.1 | Section 5 of the CT course notes (basic combinatorics); Sections 2.4 (string combinatorics) and 5.2 (number of global alignments) of the BielefeldSeqAnLN. | |
| 5 | Fri, 21/3/2014 (2h) | String combinatorics and basic combinatorics cont'd; saving space for global alignment; DP-algorithm of Smith-Waterman for local alignment | S&M 3.2.1, 3.2.2, J&P 6.8 | ||
| 6 | Wed, 26/3/2014 (3h) | Introduction to algorithm analysis, Big-Oh notation (slides), semiglobal alignment, affine gap functions (sketch) | S&M 2.3, 3.3.3; J&P 2.8, 6.9 | Section 2.3 of the BielefeldSeqAnLN. Section 4 (except 4.3) of the CT course notes. It is highly recommended that you do the exercises in Section 4.4.; slides on Big-Oh notation. | |
| 7 | Fri, 28/3/2014 (2h) | Multiple sequence alignment 1: motivation, definition, induced alignments, sum-of-pairs score | S&M 3.4.1, J&P 6.10 | Chapter 13 of the BielefeldSeqAnLN. (Careful, here it is all done w.r.t. edit distance, not alignment score, but the ideas are the same!) | |
| 8 | Wed, 2/4/2014 (3h) | Multiple sequence alignment 2: DP algorithm for MSA, analysis; 1st heuristic for MSA: star alignment | S&M 3.4.1, 3.4.2 | Chapter 14.1.1 (DP) of the BielefeldSeqAnLN. (Careful, here it is all done w.r.t. edit distance, not alignment score, but the ideas are the same!) | |
| 9 | Fri, 4/4/2014 (2h) | Multiple sequence alignment 3: progressive alignment (2nd heuristic for MSA) | J&P 6.10 | Chapter 16 of the BielefeldSeqAnLN (parts only). (Careful, here it is all done w.r.t. edit distance, not alignment score, but the ideas are the same!) Here is the example from class for an alignment of alignments. | |
| 10 | Fri, 11/4/2014 (2h) | MSA cont'd: analysis of heuristic algorithms; Scoring matrices 1: PAM-matrices | 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). You can read the original article on PAM matrices (more exactly, book chapter), by Margret Dayhoff et al, 1978. It is very understandable! | |
| 11 | Wed, 23/4/2014 (2h) | Scoring matrices 2: PAM-matrices cont'd; BLOSUM matrices (sketch) | S&M 3.5.1; J&P 3.7 | Here is the BLOSUM62 matrix. 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). | |
| 12 | Thu, 24/4/2014 (2h) | Introduction to project/presentation topics. | See the projects page. | ||
| 13 | Wed, 30/4/2014 (2h) | Midterm exam (lectures 1-11). | 8.15-10.15, in aula F. (Please be there a bit ahead of time and bring a photo ID.) Here is a list of what you need to know. It is highly recommended that you re-do all the exercises given during the lectures (both regular and homework), and that you go through the CT course notes (esp. Sections 3.1, 4 except 4.3, and 5) and do the exercises in Section 4.4. Exam results. | ||
| 14 | Fri, 2/5/2014 (2h) | Discussion of exam. Sequence comparison in practice: dotplots, BLAST (introduction). | J&P 9.6, S&M 3.5.2 | Chapter 6 (in part. 6.1: dotplots, 6.4.2: BLAST) of the BielefeldSeqAnLN. There are some nice dotplots, with good explanation, in the book by Mount, see here. | |
| 15 | Wed, 7/5/2014 (2h) | Sequence comparison in practice 2: BLAST. | S&M 3.5.2, J&P 9.8 | Chapter 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). There is a very detailed section on BLAST in the book by Mount (full ref. see main page of course), within chapter 7, p. 300 onwards. | |
| 16 | Fri, 9/5/2014 (2h) | Basic statistics 1: descriptive statistics vs. inferential statistics, types of data, sample vs. population, measures of center, measures of variability | Aczel&S., ch. 1 | Amir D. Aczel and Jayavel Sounderpandian, Complete Business Statistics, Seventh Edition, 2009; Marco Bramanti, Calcolo delle Probabilità e Statistica, Teoria ed esercizi, 1997. Here is a nice handout from Radford University (downloaded from www.radford.edu/jkell/statsgraphs.pdf) about the use of statistics in biology. | |
| 17 | Fri, 16/5/2014 (2h) | Basic statistics 2: displaying data, different types of graphs in common use, examples, misuses | Aczel&S., ch. 1, Bram 1.1-1.5 | There is this nice website at the Biology Department of the University of Leicester, which explains many statistical concepts. We also looked at several ways in which statistics can be displayed in misleading ways on this website. (The title "Lies, damned lies, and statistics" is a citations from Mark Twain.) In particular, we looked at examples for manipulating the x-axis (36), manipulating the y-axis (4), selecting misleading time frames (43,3), and mixing different scales on the y-axis in one graph (5). | |
| 18 | Fri, 23/5/2014 (2h) | Basic statistics 3: hypothesis testing 1: null hypothesis, errors type I and type II, p-value, significance of a test, power of a test | Aczel&S. ch. 7, Bram 4.4 | ||
| 19 | Wed, 28/5/2014 (2h) | Basic statistics 4: hypothesis testing 2, one-tailed vs. two-tailed tests, Z-statistic, using tables | Aczel&S. ch. 7, Bram 4.4 | ||
| 20 | Fri, 30/5/2014 (2h) | Introduction to phylogenetics: types of phylogenetic trees, types of input data | Lecture Notes on Phylogenetics from the University of Bielefeld: BielefeldPhyloLN (see on top of this page): ch. 1; Felsenstein book (see main page of course), ch. 1; S&M pp. 175-177; here is the handout of Haeckel's tree of life (source: Wikimedia Commons). | ||
| 21 | Tue, 3/6/2014 (2h) | Formal definition of trees, properties of trees, number of phylogenetic trees. | BielefeldPhyloLN ch. 2, Felsenstein ch. 3 (pp. 19-25) | ||
| 22 | Wed, 4/6/2014 (2h) | Perfect Phylogeny, Parsimony (Small Parsimony vs. Large Parsimony) | BielefeldPhyloLN ch. 3 (partially), Solution to exercise: Is this a PP? | ||
| 23 | Fri, 6/6/2014 (2h) | Fitch' algorithm for Small Parsimony | BielefeldPhyloLN ch. 4 (up to 4.2), Felsenstein ch. 2 (pp. 11-13) | ||
| -- | Mon+Tue, 9+10/6/2014 | Presentations by students | See here for a full program. | ||
| 24 | Fri, 13/6/2014 (2h) | Second written exam | Here is a list of what you need to know. | ||
| -- | Mon+Thu, 14+17/7/2014 | Presentations by students | See here for a full program. | ||
| -- | Mon+Thu, 21+22/7/2014 | Presentations by students | See here for a full program. |
