Fundamental Algorithms for Bioinformatics: Bioinformatics Algorithms

Fundamental Algorithms for Bioinformatics: Bioinformatics Algorithms
(academic year 2017/2018, second term)

Masters in Medical Bioinformatics

Title of course:	Bioinformatics Algorithms (Module 2 of Fundamental Algorithms for Bioinformatics)
Lecturer:	Zsuzsanna Lipták
email:	zsuzsanna DOT liptak AT univr DOT it
Course times:	Thu 11.30 - 13.30 (aula I) (starts at 11:45) Fri 11.30 - 14.30 (aula C) (ends at 14:15)
Student hours:	Wed 10.00-12.00 and by appointment
Office:	Ca' Vignal, 2, 1st floor, right corridor, office 1.79

News:

Written exam on 22 June and 25 July 2018, 9-12 in the morning.
Here is what you need to know for the exam: Study list for students of Medical Bioinformatics and for students of Molecular and Medical Biotechnology.
Note for the exam: Please arrive a bit ahead of time and make sure you have identification (with photo) with you. You are not allowed to use any material or notes, and can only use the paper provided in the exam.

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.

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

Introduction

Pairwise Sequence Analysis

Pairwise sequence alignment (global, local, other variants)
String distances
q-grams and de Bruijn graphs
Pairwise alignment in practice: BLAST, Scoring matrices

Multiple sequence alignment

SP-score, DP algorithm
Star alignment (heuristic, approximation)
Progressive alignment

Sequence Assembly

Sequence Assembly via SCS
Sequencing by Hybridization and NGS: de Bruijn graphs, Euler tours

Phylogenetics algorithms

Distance based methods: UPGMA, NJ
Character based methods: Perfect Phylogeny, Small Parsimony, Large Parsimony

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 now 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.
Lecture notes on Phylogenetics by Jens Stoye and others, Bielefeld University, Germany.

Lectures

Disclaimer: Here I list the topics which we covered in the lectures, and put up slides if there are some, 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 are slides)

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 mistakes, please let me know!

No.	Date	Topic	Slides (if any)	Supporting material or chapters in books, comments
1	Thu, 1/3/2018	Organisation of course. Introduction: Strings and sequences in Biology and in Computer Science.	Organisation (printable), Strings and Sequences in Biology (printable), Strings and Sequences in Computer Science (printable)
2	Thu, 8/3/2018	Pairwise alignment I: Number of alignments: recursion, explicit exponential lower bound, exhaustive search. Needleman-Wunsch DP-algorithm for global alignment, analysis.	Pairwise Alignment (printable, part 1)	This and the following lectures follow pretty closely chapter 3 of the Setubal & Meidanis book. (The Ohlebusch book and the Bielefeld Lecture Notes on Sequence Analysis both use distance functions instead of similariy functions for their presentation of alignment algorithms.) Number of alignments: Bielefeld Lecture Notes on Sequence Analysis (see above), appendix B.
3	Fri, 9/3/2018	Pairwise alignment II: Backtracing without and with traceback pointers. Space-saving variant of NW-algorithm. Local alignment: Smith-Waterman algorithm.	same as before; (printable, part 2)	global al.: Setubal & Meidanis, ch. 3.2.1, local al.: ch. 3.2.2
4	Thu, 15/3/2018	Pairwise Alignment III: Semiglobal alignment. Affine gap functions in quadratic time and space.	Pairwise Alignment 2 (printable, part 1, printable, part 2)	semiglobal al.: Setubal & Meidanis, ch. 3.2.3 Correction of handout slides: on p.3 the score of the right alignment is -1 (not -3)
5	Fri, 16/3/2018	Pairwise Alignment IV: Affine gap functions, cont'ed (example). Computing an optimal pairwise alignment in linear space via Divide-and-Conquer.	Pairwise Alignment 3 (printable)	affine gap functions: Setubal & Meidanis, ch. 3.3.3
6	Thu, 22/3/2018	Pairw. alignment IV cont'ed: Computing an optimal pairwise alignment in linear space, cont'ed. String distances I: edit distance.	same as before	D&C algorithm for optimal al. in linear space: Bielefeld Lecture Notes on Sequence Analysis, ch. 5.4.; (a different algorithm for optimal al. in linear space: Setubal & Meidanis, ch. 3.3.1, and Ohlebusch ch. 8.1.2) String distances: Bielefeld Lecture Notes Seq. Analysis, ch. 3
7	Fri, 23/3/2018	String distances II: metric, DP algorithm for computing the edit distance, Connection between edit distance and alignment score, LCS-distance, Hamming distance.	String distances (printable)	distance vs. similarity: Setubal & Meidanis ch. 3.6.1, Ohlebusch ch. 8.1.4 and 8.1.5
8	Thu, 5/4/2018	String distances III: The q-gram distance.	The q-gram distance (printable)	q-gram distance: Bielefeld Lecture Notes on Sequence Analysis, ch. 3.7
9	Fri, 6/4/2018	De Bruijn sequences and de Bruijn graphs I: de Bruijn sequences over different alphabets, existence of de Bruijn sequences.		see class notes and slides for Lecture 22 (2) and the Compeau et al. article there
10	Thu, 12/4/2018	De Bruijn sequences and de Bruijn graphs II: (full) de Bruijn graphs, construction of de Bruijn sequences via Euler tours.		see class notes and slides for Lecture 22 (2) and the Compeau et al. article there
10a	Thu, 12/4/2018	Extra lecture: Computational Efficiency I.	Computational Efficiency 1 (printable)
11	Fri, 13/4/2018	De Bruijn sequences and de Bruijn graphs III: de Bruijn subgraphs and sequences with q-gram distance 0.		Bielefeld Lecture Notes on Sequence Analysis ch. 3.7
12	Fri, 20/4/2018	Scoring matrices: PAM, BLOSUM.	Scoring Matrices (printable)	Setubal & Meidanis, ch. 3.5.1 Here are two PAM mutation matrices, and two PAM scoring matrices (the ones handed out in the lecture). You can read the original article on PAM matrices (more exactly, book chapter), by Margret Dayhoff et al, 1978. It is very understandably written! Here is the BLOSUM62 matrix. See also this nice little article by Sean Eddy about the BLOSUM matrices (S. Eddy, Where did the BLOSUM62 alignment score matrix come from? Nature Biotechnology 22, pp. 1035-1036, 2004).
12a	Fri, 20/4/2018	Extra lecture: Computational Efficiency II.	Computational Efficiency 2 (printable)
13	Thu, 3/5/2018	Multiple Sequence Alignment (MSA) I: definitions, projections, scoring, sum-of-pairs score, theorem about optimal projections and optimal MSAs.		Setubal & Meidanis, ch. 3.4.1, Ohlebusch, ch. 8.2
14	Fri, 4/5/2018	MSA II: DP-algorithm, Star Alignment Algorithm		DP-algorithm: Setubal & Meidanis, ch. 3.4.1, Bielefeld Lecture Notes on Sequence Analysis: ch. 11.1, Ohlebusch 8.2 star alignment for similarity score: Setubal & Meidanis, ch. 3.4.2
15	Thu, 10/5/2018	MSA III: star alignment as a 2-approximation algorithm (for edit distance, and in general, for distance functions with triangle inequality)		star alignment as a 2-approximation: Ohlebusch, ch. 8.2.2, Bielefeld Lecture Notes on Sequence Analysis, ch. 11.3
16	Fri, 11/5/2018	MSA IV: progressive alignment		Bielefeld Lecture Notes on Sequence Analysis: Appendix H.1, Ohlebusch ch. 8.2.3
17	Thu, 17/5/2018	Jens Stoye (Univ. Bielefeld): Phylogenetics I: Introduction. Character-based methods. Definitions, perfect phylogeny (PP), Gusfield's algorithm for binary characters. Small Parsimony: Fitch' algorithm.		Bielefeld Phylogenetics Lecture Notes, ch. 2 (Introduction), ch. 3 (characters and states), ch. 4 (Perfect Phylogeny, Gusfield's algorithm), ch. 5.2 (Fitch' algorithm)
18	Fri, 18/5/2018	Jens Stoye (Univ. Bielefeld): Phylogenetics II: distance-based methods. UPGMA, Neighbor Joining (NJ).		Bielefeld Phylogenetics Lecture Notes, ch. 7 (7.1, 7.3.1 and 7.3.4)
19	Thu, 24/5/2018	Phylogenetics III: Number of rooted and unrooted trees. More on distance based methods: ultrametric matrices, 3-point condition, and rooted trees; additive metrics, 4-point conditon, and unrooted trees.	Phylogenetics 1 (printable)	same as previous lecture
20	Fri, 25/5/2018	Phylogenetics IV: More on character-based methods: homoplasies and the definitions of compatibility and perfect phylogeny (PP); parsimony problem: Large Parsimony and Small Parsimony; characterization of PP via number of state-changes.	Phylogenetics 2 (printable)	same as lecture 17
21	Thu, 31/5/2018	Phylogenetics IV cont'ed: Algorithms for Large Parsimony: Greedy Sequential Addition Algorithm, Branch-and-Bound Algorithm, Nearest Neighbor Interchange.	same as before	Large Parsimony (=Maximum Parsimony): Bielefeld Phylogenetics Lecture Notes, ch. 6.3 (Greedy Sequential Addition, NNI); for the branch-and-bound algorithm that we did, see here an excerpt from the Felsenstein book (pages 61 to 64). Correction of handout slides: Note that we did three algorithms for Large Parsimony (and not two, as it said on the handout slides!)
22	Fri, 1/6/2018	Two more applications of q-grams: (1) Database search with BLAST. (2) Sequence Assembly with de Bruijn graphs.	BLAST (summary only!) (printable) Fragment Assembly with de Bruijn graphs (printable)	(1) Here is the orginal article on BLAST: S.F. Altschul et al. Basic Local Alignment Search Tool, J. Mol. Biol. 215: 403-410 (1990); and the one on BLAST2: S.F. Altschul et al. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, Nucleic Acids Research, Vol. 25, No. 17: 3389-3402 (1997). There is a very detailed section on BLAST in the book by Mount (full ref. see above), within chapter 7, p. 300 onwards. BLAST is also described in Chapter 6.3 of the BielSeqAn Lecture Notes (see above). There are excellent help pages on the NCBI Blast page, among them on how to submit a request and how to read the results (version of Sept. 2016, always get the latest one!). (2) See this article: How to apply de Bruijn graphs to genome assembly by Phillip E.C. Compeau, Pavel A. Pevzner, and Glenn Tesler, Nature Biotechnology, vol. 29 no. 11 (Nov. 2011); there is also supplementary material for this article.
23	Fri, 8/6/2018	Summary of course.		Study list for students of Medical Bioinformatics and for students of Molecular and Medical Biotechnology.