(academic year 2014/2015)

Title of course: | Algoritmi e Linguaggi per Bioinformatica: Algoritmi (2nd term of 2014/2015) (Institutional page) |

Lecturer: | Zsuzsanna Lipták |

email: |
zsuzsanna DOT liptak AT univr DOT it (Please put "Corso Algoritmi di Bioinformatica" in the subject line.) |

Course times: | Wed 8.30 - 10.30 (aula Tessari) Thu 8.30 - 11.30 (aula G) |

Office hours: |
Wed 10.30-12.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?)

**News:**

- Preliminary program of project presentations for July here.
- Results of exam of 17 June 2015 here: full version and short version.
- Written exam on Tuesday, 21 July, 9-12. Please be there at 8:45 and bring along identification (with photo). You are not allowed to use a calculator, books, or notes. Please write me an email if you intend to participate!
- Here is a list of what you need to know for the exam.

**Projects:**

- Project presentation topics here.
- Here are some tips how to make a good presentation.
- Preliminary program.

**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 2014/2015), Prof. Marchetti. The total grade (voto) for the module "Algoritmi e Linguaggi per Bionformatica" will be approx. 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). **Note:** The 2x2-hour exam option is only available on those two dates! On all further dates and future exam sessions (appelli), you will have to take the full 3-hour version of the written exam, *even if you passed the first 2-hour exam in April*.

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 and/or July). And if you repeat it, then you have to take the oral exam instead.

**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 scoring 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.

**TENTATIVE SCHEDULE:**

(For the real one, please check here)

- General introduction
- Pairwise sequence alignment
**Detour:**Algorithm analysis- Multiple sequence alignment
- String similarity and distance
- Scoring matrices
- Heuristics: FASTA, BLAST
- 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.

**João Setubal, João Meidanis:***Introduction to Computational Molecular Biology*(1997).

This is my favourite book. There is one copy in the library: during the course, you can check it out for 7 days only. This book concentrates on the algorithmic angle, gives concise background on the biological motivations, and treats sidelines only briefly. It is, however, a bit too advanced for us, but everything we treat is covered (and much more).

**Neil C. Jones and Pavel A. Pevzner:***An Introduction to Bioinformatics Algorithms*(2004).

This is a book for teaching. There are 4 copies in the library, which you can check out for 7 days. 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.

**David M. Mount:***Bioinformatics: Sequence and Genome Analysis*(2004). Very extensive, contains more than you ever wanted to know! Good reference.

**Arthur Lesk:***Introduction to Bioinformatics*(2008). Application oriented, contains less than we need on some topics.

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