Here you can get back to the main page of the course.
News:
Projects:
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 first part; for details of these and of more books, see the main page of the course. For the second part, I will give pointers to the Bielefeld Phylogenetics lecture notes mostly. The most important book for this part is the book by Felsenstein.
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.
Note: Here I list the topics which we treated in the lectures, and put up slides if we have them, as well as pointers to the respective chapters in books, and possibly other material of interest. However, you will always need the class notes, too! (even if there were slides, as well)
| No. | Date | Topic | Slides (if any) |
Chapters in books | Homework | Other material (supporting material, suggested reading) |
|---|---|---|---|---|---|---|
| 1 | Wed, 4/3/2015 (2h) | Organisation of course; Overview | Organisation (print version) |
|||
| 2 | Thu, 5/3/2015 (3h) | Computational efficiency 1: Fibonacci numbers, some proofs by induction, three algorithms for computing F(n) | Comput. Efficiency 1 (print version) |
J&P 2.6 (p.31 onwards), 2.7 | See here for more on Fibonacci numbers and nature, and here for more on Fibonacci numbers and maths. | |
| 3 | Wed, 11/3/2015 (2h) | Pairwise sequence alignment 1: motivation, introduction to pairwise alignments | S&M 3.1 | BielefeldSeqAnLN (see above) ch. 1 | ||
| 4 | Thu, 12/3/2015 (3h) | Pairwise sequence alignment 2: some string formalism, counting strings, number of alignments | S&M 2.1 (p.33-34) | Compute N(n,m) for 1 <= n,m <= 4 | BielefeldSeqAnLN (see above) ch. 2.4 | |
| 5 | Wed, 18/3/2015 (2h) | Pairwise sequence alignment 3: Needleman-Wunsch algorithm for global alignment | S&M 3.2.1, J&P 6.6 | Global alignments: solution | ||
| 6 | Thu, 19/3/2015 (3h) | Pairwise sequence alignment 4: Analysis of Needleman-Wunsch algorithm, space saving variant, Smith-Waterman algorithm for local alignment | S&M 3.2.2 | Local alignment: solution | ||
| 7+8 | Wed+Thu, 25+26/3/2015 (5h) | Computational efficiency 2: Algorithm analysis and Big-O-notation, on the example of Needleman-Wunsch DP algorithm vs. Exhaustive search for pairwise alignment Pairwise sequence alignment 5: affine gap functions (sketch, no algo) |
Comput. Efficiency 2 (print version) |
S&M 2.3, J&P 2.8 J&P 6.9, S&M 3.3.3 |
(1) Space of Exh. Search algo (2) Section 4.4 in the CTnotes (3) How long does computing the Hamming distance take? |
Please read sections 4.1 and 4.2 of the CTcourse notes and solve all exercises in Section 4.4 (except ex. 3). It is also useful to read (and understand!) Section 2 (What is an algorithm) and Section 5 (Some basic maths). BielefeldSeqAnLN (see above) ch. 2.4. |
| 9 | Wed, 1/4/2015 (2h) | String distance measures: edit distance, computation of edit distance | String Distance (print version) ex. on p. 18 corrected |
S&M 3.6.1, J&P 6.4 | (1) Show that the Hamming distance is a metric (2) finish edit distance DP-table for example ACCT, CACT |
|
| 10 | Wed, 8/4/2015 (2h) | String distance measures cont'ed: connection between edit distance and alignment score, LCS distance | ||||
| 11 | Thu, 9/4/2015 (3h) | Scoring matrices: PAM matrices | S&M 3.5.1; J&P 3.7 | Solution of ex. 6 of the CT notes, for which we didn't have time in class. | 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! 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). |
|
| -- | Wed&Thu 15+16/4/2015 | Research Days (no lecture) | ||||
| 12 | Wed, 22/4/2015 (2h) | Summary of first half: 1. Sequence similarity, 2. Computational efficiency | ||||
| 13 | Thu, 23/4/2015 (2h) | Midterm exam in aula E |
You are not allowed to use any material (books, notes), and no calculator. You can only use the paper provided by us. Please bring along a photo ID (foto tessera), with your name, photo, and matricola. Results here. |
|||
| 14 | Wed, 29/4/2015 (2h) | Database search: BLAST | S&M 3.5.2, J&P 9.6 | Here is the orginal article on BLAST: S.F. Altschul et al. Basic Local Alignment Search Tool, J. Mol. Biol. 215: 403-410 (1990); and the one on BLAST2: S.F. Altschul et al. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, Nucleic Acids Research, Vol. 25, No. 17: 3389-3402 (1997). 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. BLAST is also described in Chapter 6.4.2 of the BielefeldSeqAnLN. |
||
| 15 | Thu, 30/4/2015 (3h) | BLAST cont'ed: the NCBI BLAST website. Overview of project presentation topics |
There are excellent help pages on the NCBI Blast page, among them on how to submit a request and how to read the results. Here is a list of the project/presentation topics. |
|||
| 16 | Wed, 6/5/2015 (2h) | BLAST summary; Phylogenetics Introduction |
BLAST (print version) (only summary!) |
|||
| 17 | Thu, 7/5/2015 (3h) | Phylogenetics Introduction (cont'ed): Brief history of phylogenetics, types of phylogenetic trees, goals and issues | BielefeldPhyloLN ch. 1 and 2.3.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). Here is the article from Nature on the issues surrounding the phylogeny of whales which I handed out in class: Zhexi Luo: In search of the whales' sisters. Nature vol 404: p. 235-239, 2000. Please read this article. We will discuss it at the end of the course. |
||
| 18 | Wed, 13/5/2015 (2h) | Introduction to trees. | BielefeldPhyloLN ch. 2. | |||
| 19 | Thu, 14/5/2015 (3h) |
Number of phylogenetic trees. Discussion of midterm exam. |
BielefeldPhyloLN 2.4 | Felsenstein ch. 3 (pp. 19-25): number of phylogenetic trees. Results of midterm exam here. |
||
| 20 | Wed, 20/5/2015 (2h) | Distance data: ultrametric and additive matrices. | BielefeldPhyloLN ch. 6 (partially) | Homework | S&M ch. 6.5 (much more detailed than what we are doing!). | |
| -- | Thu, 21/5/2015 | San Zeno (no lecture) | ||||
| 21 | Wed, 27/5/2015 (2h) | Algorithm UPGMA for ultrametric trees. Character data: Perfect Phylogeny. |
BielefeldPhyloLN ch. 6.2 | Example on UPGMA: page 1 and page 2. Example: Is this a PP? |
There is a very nice description of UPGMA and the molecular clock assumption in the book by Durbin et al., ch. 7.3, pp. 166-170; Felsenstein-book ch. 11 (p. 161-166). | |
| 22 | Thu, 28/5/2015 (3h) |
Character data: Compatibility, Parsimony. Discussion of the Nature article on whales. |
Phylogenetics (summary) (print version) |
BielefeldPhyloLN ch. 3 | Felsenstein ch. 1. Article on the phylogeny of whales which I handed out in class: Zhexi Luo: In search of the whales' sisters. Nature vol 404: p. 235-239, 2000. |
|
| -- | Wed, 17/6/2015 (2 or 3h) | Second written exam | Second partial exam of 2h (or full exam of 3h) on Wed 17 June 2015, 9-12, in aula Tessari. Please write me an email if you want to take the long version. Here is what you need to know for the exam. Results: full version and short version. | |||
| -- | Mon, Tue, Wed 8+10+11/6/2015 | Presentations by students | See here for a full program. | |||
| -- | Wed, Thu, Fri 22+23+24/7/2015 | Presentations by students | See here for a full program. |
