Algorithms for Computational Biology
(academic year 2015/2016)

Masters in Molecular and Medical Biotechnology

News:

• Here is a list of what you need to know for the exam: study list (no guarantee of completeness!)
• Next student hours: Fri Jan 22, 15:30-17:30, and Fri Jan 29, 13:30-15:30
  Note: If you want to talk about something other than the contents of the exam, then please make an appointment!
• Written exams (3 hours): 1 Feb (followed by orals on 3 Feb.), and 29 Feb (followed by orals same week). If you pass the written exam on 1 Feb., then you have the choice of taking the oral on 3 Feb. or in the week after 29 Feb. You can also re-take the written exam on 29 Feb. but then your previous result will be cancelled.
• Lecture contents updated (18 Jan), incl. a big example for UPGMA and one for PP (see below).
• Tips for how to make a good project presentation here.
• Project topics here (updated 18 Jan).

GOALS of the course:

1. to learn about some basic problems and algorithms behind common bioinformatics applications (sequence alignment, sequence similarity, phylogenetics), and
2. to get an idea of some basic computational issues (problem specification, efficiency of algorithms, limitations).

CREDITS: 6 CFU, written exam, followed by oral exam. You are admitted to the oral exam only if you passed the written exam. For those who want this course to count for the future Masters in Medical Bioinformatics (Dip. Inf.): it can replace the second part (6 CFU) of the course "Fundamental Algorithms in Computational Biology" only if you do an additional assignment on a topic from algorithms in computational biology (to be chosen together with the lecturer).

LANGUAGE: Lectures are in English; however, questions can be asked in English or Italian. Written exams will be in Italian only, unless an English version is requested by the students; answers can be given in Italian or in English, main thing that they be legible.

A note on ATTENDANCE: As in most university courses, attendance of classes is not mandatory. All of what I teach in this course is completely standard and is contained in any algorithmically oriented bioinformatics book (see e.g. list on this page). In the exam, you will be asked to do things like compute an alignment of two strings, given a scoring function. You can learn this from any book or online course. However, I believe that one gains much more from attending a course than from only studying by oneself. University classes give the student the opportunity of following a live course given by a live lecturer. If nothing else, attending the course forces you to spend a certain amount of time each week with this course. No handouts or slide presentations can completely substitute a lecturer. So if you can make it, I would advise you to attend. If you can't, you have to rely on the notes of your colleagues and/or on books.

SYLLABUS:

• General introduction
Part I: Sequence analysis and algorithms
• Pairwise sequence alignment
• Detour: Algorithm analysis
• Multiple sequence alignment
• String similarity and distance
• Scoring matrices
• Heuristics: BLAST
Part II: Phylogenetics
• Introduction
• Detour: Trees and graphs
• Algorithms for distance-based data
• Character-based data, Perfect Phylogeny
• Small Parsimony: Fitch's algorithm
• Large Parsimony: heuristics

SUGGESTED BOOKS:

On bioinformatics:
• João Setubal, João Meidanis: Introduction to Computational Molecular Biology (1997).
  My favourite book, even though a bit dated, and more of a research book than a teaching book.
  
• Neil C. Jones and Pavel A. Pevzner: An Introduction to Bioinformatics Algorithms (2004).
  We have 3 copies in the library.
  
• David M. Mount: Bioinformatics: Sequence and Genome Analysis (2004).
  Biological point of view. Very extensive, contains more than you ever wanted to know! Good reference, but not always detailed enough on algorithms.
  
• Dan Gusfield: Algorithms on Strings, Trees, and Sequences (1997).
  This is the book on string algorithms. On top of being a very thorough book on string algorithms, it also explains at length applications, of each problem and algorithm, in computational biology.
  
• Joseph Felsenstein: Inferring Phylogenies (2004).
  This is the standard book on phylogenetics. Very nice reading, precise but not too formal.
  
• R. Durbin, S. Eddy, A. Krogh, G. Mitchinson: Biological Sequence Analysis (1998).
  This is a very nice algorithmic book, with an emphasis on probabilistic models.
  
  
On algorithms:
• Cormen, Leiserson, Rivest (& Stein): Introduction to Algorithms (different editions, 1990-onwards).
  This is the "bible" on algorithms. Always good to have a look.
  
  
These two lecture notes from my old university Bielefeld can also be useful (below I will give the respective chapters if applicable):
• Lecture notes on Sequence Analysis by Jens Stoye and others, Bielefeld University, Germany.
• Lecture notes on Phylogenetics by Jens Stoye and others, Bielefeld University, Germany.

EXAM: Written exam, followed by oral exam (only if you passed the written exam).

Lectures

Disclaimer: 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)

In the table below, the following abbreviations are used (for full details of the books, see above):

• S&M = Setubal and Meidanis, 1997
• J&P = Jones and Pevzner, 2004
• BielSeqAn = Lecture notes on Sequence Analysis, Bielefeld University
• BielPhylo = Lecture notes on Phylogenetics, Bielefeld University