Algoritmi e Linguaggi per Bioinformatica: Algoritmi

Attention!     This is the webpage of the course given in the 2nd term of 2011/2012.
The new course (2nd term 2012/13) may have a different webpage.

News:     Appello 8 e 25 febb 2012:

• Gli esami si terrano in lingua italiana o in lingua inglese (se richiesto dallo studente).
• Per tutta la comunicazione (email ecc.) si puo' usare o l'italiano o l'inglese.
• written exams: on 8 Sept and 25 Feb. 2013. Please send me an email a few days before to let me know that you want to participate!
• oral exams: Individual date/time. Please write me an email and we will fix a date and time.

Goals of the course: 1. to learn about some basic problems and algorithms behind common bioinformatics applications (alignment, sequence similarity, phylogenetics), and 2. to get an idea of some basic computational problems (complexity, efficiency, limitations).

Credits: The credits for this course are given together with the first part of this module (Linguaggi, 1st term 2011/2012). The total grade (voto) for the module "Algoritmi e Linguaggi per Bionformatica" will be 50% Linguaggi and 50% Algoritmi. The grade (voto) for this course (Algoritmi) is given in the following way: 50% written exam, 50% project. The written exam consists of 2 parts: one midterm (which covers the first half of the course) and one final (which covers the second half). Alternatively, one can take only one final exam (which covers the whole course). The project can be done in groups of 1 to 3, and will be chosen together according to the students' backgrounds and interests.

Language: Lectures are in English; however, questions can be asked in English or Italian. Exams will be in Italian only (but answers can be given in English if you choose).

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 list on this page). In the exam, you will be asked to do things like compute an alignment of two strings, given a score function. You can learn this from any book or online course. However, I strongly 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 studying for this course. No handouts or slide presentations can completely substitute a lecturer. So if you can in any way 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.

Tentantive schedule (updated):
(For the real one, please check here)

• Pairwise sequence alignment
• Algorithm analysis
• Scoring matrices
• Heuristics: FASTA, BLAST
• String similarity and distance
• ---Midterm exam---
• Phylogenetics: distance-based data, character-based data,
  Perfect Phylogeny, Small Parsimony, Large Parsimony
• Some statistics for bioinformatics
• ---Final exam---

Books: There are many books on bioinformatics, and most, if not all, will contain what we cover in this course. The following is a selection of my own.

• João Setubal, João Meidanis: Introduction to Computational Molecular Biology (1997).
  This is my main reference. There is one copy in the library and soon there will be two; you will be able to check them out for a maximum of 3 days during the course. I personally really like this book. It concentrates on the algorithmic angle, gives concise background on the biological motivations, and treats sidelines only briefly. It is concise and good for teaching. It is unfortunately a bit dated, so some current topics are not treated (but everything we cover is).
• Neil C. Jones and Pavel A. Pevzner: An Introduction to Bioinformatics Algorithms (2004).
  There are 4 copies in the library, which you can check out for 3 days. I don't use this book very much, but I will try to give the corresponding chapters for each lecture.
• Arthur Lesk: Introduction to Bioinformatics (2008).
  This is a much more practical bioinformatics book, which is more concerned with applications. It is very teaching/learning oriented.
  Update: I no longer think that this book's depth of coverage suffices for this course. But I still believe it's a nice book for its orientation towards the applications.
• 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.
• Hans-Joachim Böckenhauer and Dirk Bongartz: Algorithmic Aspects of Bioinformatics (2010).
  This is a very mathematical book, more for research than for teaching, interesting mainly for those with a mathematical/computer science background who want to continue in this field. Also includes recent research areas such as haplotyping and genome rearrangements.
• Dan Gusfield: Algorithms on Strings, Trees, and Sequences (1997).
  This is the book on string algorithms.
• Joseph Felsenstein: Inferring Phylogenies (2004).
  This is the standard book on phylogenetics.
• Update: Finally, the "bible" on algorithms: Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (different editions, 1990-onwards) which is always a good place to look for anything about algorithms.