Note: This page will be updated every week as the course progresses.



Algoritmi e Linguaggi per Bioinformatica: Algoritmi
(academic year 2012/2013, spring 2013)

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.

Schedule

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).