Fundamental Algorithms for Bioinformatics: Bioinformatics Algorithms
(academic year 2018/2019, II semester)

Masters in Medical Bioinformatics

News:

• All slides up now, also some homework. Please note that I handed out a set of example exercises during the last class. If you don't have them, come by and I'll give you a copy.
• Here is what you need to know for the exam: Study list for students of Medical Bioinformatics (update!) and for students of Molecular and Medical Biotechnology.
• See here for the slides of Joe Sawada's talk: talk.

GOALS of the course: To learn about some of the basic problems and algorithms behind common bioinformatics applications (sequence alignment, sequence similarity, sequence assembly, phylogenetics).

CREDITS: 12 CFU, together with module 1 of this course (Algorithm Design). This module contributes half of the grade. It is gained via a written exam, followed by oral exam. You are admitted to the oral exam only if you passed the written exam.

If you are taking this course as a student of Molecular and Medical Biotechnology (LM9) ("mutuazione Algorithms for Computational Biology"), then you will get 6 CFU (credits) for this course, and will have a different exam to take. However, it still holds that you have to take a written and an oral exam.

MATERIAL: When there are slides, I hand them out and put them up on the webpage. However, we always do more in class than what is on the slides: examples, missing proofs, additional material, illustrations, applications, etc. So you will always also need your class notes (or someone else's).

HOMEWORK: I regularly give you homework, and I expect you to do it. If you do not, you will not gain the experience in solving exercises that you need for the exam.

SYLLABUS:
Here is an overview of the topics that will be covered. The topics and the order may vary slightly.

• Pairwise Sequence Analysis
  • Pairwise sequence alignment (global, local, other variants)
  • String distances (edit distance, LCS, q-gram distance)
  • Pairwise alignment in practice: BLAST, Scoring matrices
• Multiple sequence alignment
  • SP-score, DP algorithm
  • Heuristic and approximation algorithms (Star alignment, progressive al.)
• Sequence Assembly
  • Sequence Assembly via SCS (recap)
  • Sequencing with de Bruijn graphs (SBH, NGS)
• Phylogenetics algorithms
  • Distance based methods: UPGMA, NJ
  • Character based methods: Perfect Phylogeny, Small Parsimony, Large Parsimony
• Introduction to string data structures
  • Basics of Suffix Trees and Suffix Arrays
  • Some applications

SUGGESTED BOOKS:

On bioinformatics algorithms:
• Enno Ohlebusch: Bioinformatics Algorithms (2013).
  This is a very nice book, covering most (but not all) topics of this course, as well as some of Module 1 of Fundamental Algorithms. It is available only online here. It is also the main textbook for my course on Computational Analysis of Genomic Sequences (2nd year). (particularly recommended) There are 3 copies in the library.
  
  
• João Setubal, João Meidanis: Introduction to Computational Molecular Biology (1997).
  My old favourite, even though a bit dated now. (particularly recommended)
  
  
• Neil C. Jones and Pavel A. Pevzner: An Introduction to Bioinformatics Algorithms (2004).
  Basic level, contains many topics of this course. We have 3 copies in the library.
  
  
• Hans-Joachim Böckenhauer and Dirk Bongartz: Algorithmic Aspects of Bioinformatics (2010). Also a nice book, detailed.
  
  
• Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, Alexandru I. Tomescu: Genome-Scale Algorithm Design. Cambridge University Press (2015). Very recent, very good, a bit too advanced for this course. Suggested if you wish to go on to research in the area of bioinformatics algorithms.
  
  
• David M. Mount: Bioinformatics: Sequence and Genome Analysis (2004).
  Biological point of view. Very extensive, contains more than you ever wanted to know (but were afraid to ask)! 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 strings and sequences, 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.
  
  
• Richard Durbin, Sean Eddy, Anders Krogh, Graeme Mitchinson: Biological Sequence Analysis (1998).
  This is a very nice algorithmic book, with an emphasis on probabilistic models.
  
  
On algorithms in general:
• Cormen, Leiserson, Rivest (& Stein): Introduction to Algorithms (different editions, 1990-onwards).
  This is the "bible" on algorithms. Always good to have a look, always good to own a copy (buy second-hand: not necessary to have the most recent edition). (recommended)
  
  
These lecture notes from my old university Bielefeld may also be useful (below I will give the respective chapters whenever applicable):
• Lecture notes on Sequence Analysis by Jens Stoye and others, Bielefeld University, Germany (2015).
• Lecture notes on Phylogenetics by Jens Stoye and others, Bielefeld University, Germany (2016).

Lectures

Disclaimer: Here I list the topics which we covered in the lectures, include the slides, pointers to the respective chapters in books, and possibly other material of interest. However, remember that the slides are not enough for studying! You always need your class notes and exercises and/or books.

When I include corrections of slides, this refers to the handed out version. The slides which you can download here have already been corrected. If you find any further mistakes, please let me know!