Algoritmi e Linguaggi per Bioinformatica: Algoritmi
(academic year 2013/2014)
|Title of course:|| Algoritmi e Linguaggi per Bioinformatica: Algoritmi (2nd term of 2013/2014)
zsuzsanna DOT liptak AT univr DOT it
(Please put "Corso Algoritmi di Bioinformatica" in the subject line.)
||Wed 8.30 - 10.30 (aula F)
until 2 April in addition: Wed 10.30-11.30 (aula B)
Fri 8.30 - 10.30 (aula F)
|Thu 12.30-14.30 (during term time)
and by appointment
(or just come by my office, I'm there most of the time)
|Office:||Ca' Vignal, 2, 1st floor, right corridor, stanza 1.79
Current information on course here: schedule, materials.
(Are you looking for last year's course?)
- Appello 16/9/2014: There will be a written exam of 3 hours on Tue 16/9 from 9:00 to 12:00 on the part "Algoritmi" (in Italian). For those wanting to take an oral exam on Algoritmi, please contact me via email between Fri 12/9 and Monday 15/9 (not before) and I will give you an appointment between 17-19/9. For the part "Linguaggi", please contact Prof. Castellini directly.
- Appello 30/9/2014: "Algoritmi": Written exam on 30/9, 9:00-12:00. Oral exams by appointment. For the part "Linguaggi", please contact Prof. Castellini directly.
- Exam preparation: Here is a list of what you need to know for the exam (Algoritmi).
- Appello 25/7/14: If you want to take part in either Linguaggi (oral/presentation, Castellini), or Algoritmi (scritto, Lipták), please be there (aula H) at 9:00 a.m.! (This does not refer to those who are taking an oral exam Algoritmi with me.)
- Exam results (16/7/2014): see here.
- Change of times for presentations on Monday 21/7: The presentations on Monday 21/7 will take place in the afternoon 14-17h, instead of in the morning (aula H).
- Appello 10/7: Written exam Linguaggi 10/7 (Thu), 13-15, aula H. Written exam Algoritmi 16/7 (Wed), 12.30-15.30 (or -14.30 if you only take the 2 hour version, see below), aula M. If you want to participate and you haven't yet done so, then send me an email, stating which exam you want to take (A, L, or both; if A, say if 3-hour or 2-hour version, see note below). If you want to take an oral exam in this appello, and you haven't yet done so, please write me an email, too, and we'll arrange a date separately.
- Office hours: I will be available both for discussing presentations, and for having a look at the last written exam, on Mon 7/7, Tue 8/7, Wed 9/7 10-12. Please write me an email if, and which of these dates, you are planning to come, so I can better organise.
(update: If you only want to see your exam, and require only a little explanation, then you can come by on any of these dates, without prenotazione. For real discussions though, Monday is now full.)
- Exam preparation: Here is a list of what you need to know for the exam (Algoritmi).
- Exceptionally this year, there will be the possibility at both appelli in July (10/7 and 25/7), open only to those who have failed one partial exam but passed the other, to retake one partial exam only. I.e. if you passed the midterm exam but not the second partial exam, then you can choose between the full exam (3 hours) or only the second partial exam (2 hours). If you passed the second partial but not the midterm, then you can choose between the 3-hour exam or retaking the midterm only (2 hours). If you failed both exams, or if you passed both and would just like to improve your grade (voto), then you have to take the full 3-hour exam which covers the whole course. Of course, the 3-hour exam is open at all appelli to all students. Note, however, that if you opt to retake the exam, then any previous written grade will be superseded by the new grade. Also, from the autumn sessions onwards, only 3-hour exams covering the whole course will be possible.
- Exam results (13/6/2014): see here.
- Program of presentations, including preliminary program for July: program.
- Projects page here: List of projects (one topic added w.r.t. the handout, 24 April 2014). You should try to decide by, say, 9 May latest, to give you time to prepare and discuss.
- Some tips for how to prepare your project presentations. If you still haven't decided on the project, please choose one, tell me, maybe get some additional material, and then start preparing. If you have questions, come by and ask me, we'll discuss. Please send me a draft project presentation as early as possible, but try to send it max a week before the presentation date, then I can have a look at it, and maybe suggest some changes.
- Results of midterm exam here.
Projects (this option is no longer available):
- Project presentation program here.
- Here are some tips how to make a
- The project descriptions can be found here.
Note to students: If you have not yet received an email from me but you are following this course (and want to get the credits) then please send me an email, putting "corso Algoritmi di Bioinformatica" in the subject line, so I can include you in the mailing list.
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 issues (complexity, efficiency, limitations).
CREDITS: The credits for this course are given together with the first part of this module (Linguaggi, 1st term 2013/2014). 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 made up of a written part and an oral part.
The written part can either be taken as one written exam of 3 hours at the end of the course, or in two parts: one midterm (2 hours, covers the first half of the course, April), and one final exam (2 hours, covers the second half of the course, June).
The oral part consists of presenting a topic to the whole class, preferably using digital slides; we will choose the topic together, according to the student's background and interests. The presentation can be done either alone or in two (10-15 mins per person, plus questions).
Alternatively, you can take an oral exam on the complete contents of the course. Note: The presentation can be done only once, and only during one of the sessions we agree upon together (in June or July, to be agreed). And if you repeat it, then you have to take the oral exam!
LANGUAGE: Lectures are in English; however, questions can be asked in English or Italian. Written exams will be in Italian only, except if an English version is also requested; answers can be given in Italian or in English, main thing that they be legible. Presentation can be given in Italian or in English, your choice; if you choose to give it in English, then linguistic quality will not influence the grade, of course.
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.
(For the real one, please check here)
Part I: Sequence analysis and algorithms
- Pairwise sequence alignment
- Detour: Algorithm analysis
- Multiple sequence alignment
- String similarity and distance
- Scoring matrices
- Heuristics: FASTA, BLAST
Part II: Statistics
- Some basic statistics for bioinformatics
Part III: Phylogenetics (some subset of the following)
- algorithms for distance-based data
- character-based data, Perfect Phylogeny
- Small Parsimony: Fitch's algorithm
- Large Parsimony: heuristics
BOOKS: There are many books on bioinformatics, and most, if not all, will contain what we cover in this course. The following is my own selection.
Two books which are more oriented towards applications are the following. Please note that their depth of coverage of the underlying algorithms is not always sufficient for this course; however, they are valuable for their emphasis on the biological viewpoint, and their presentation of the issues and applications in very user-oriented terms:
- João Setubal, João Meidanis: Introduction to Computational Molecular Biology (1997).
This is my main reference. There is one copy in the library: during the course, you can check it out for three days only. 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.
- 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.
- Dan Gusfield: Algorithms on Strings, Trees, and Sequences (1997).
This is the book on string algorithms. On top of being a very thourough 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.
- 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.
- Cormen, Leiserson, Rivest (& Stein): Introduction to Algorithms (different editions, 1990-onwards). This is the "bible" on algorithms. Everyone interested in algorithms should have a copy of this book. Since there are so many editions around, one can easily find a cheap second hand copy.
For the statistics part, you can refer to these books:
- David M. Mount: Bioinformatics: Sequence and Genome Analysis (2004).
- Arthur Lesk: Introduction to Bioinformatics (2008).
I use the following two lecture notes from my former university Bielefeld a lot. Note that they are much more detailed than what we cover, and sometimes use different notation. They can be useful for certain topics, and I will assign some chapters for the oral presentations; when the class is exactly based on these lecture notes, then I will say so.
- Amir D. Aczel and Jayavel Sounderpandian, Complete Business Statistics, Seventh Edition, 2009;
- Marco Bramanti, Calcolo delle Probabilità e Statistica, Teoria ed esercizi, 1997.