Title of course:  Modelli Biologici Discreti/ Discrete Biological Models (Institutional page) 
Lecturer:  Zsuzsanna Lipták 
email: 
zsuzsanna DOT liptak AT univr DOT it (Please put "Corso Modelli Biologici Discreti" in the subject line.) 
Course times:  Tue 11.30  13.30 (aula C) Wed 10.30  13.30 (aula C) 
Office hours: 
Thu 8.3010.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 
News:
Old News:
GOALS of the course:
1) become familiar with some commonly used discrete models for biological phenomena/computational biology problems
2) be able to model a given biological phenomenon with strings, graphs, trees, matrices, as appropriate
3) learn some basic discrete mathematics commonly used in biological modelling (basic combinatorics, binomial coefficients, modulo arithmetics, graphs, trees)
PROGRAM:
In this course, we will study how to model biological phenomena using discrete mathematical models, i.e. different approaches for representing and solving problems from molecular biology using graphs, strings, integervalued matrices, and permutations. The topics covered in the course will be a subset of the following: overlap graphs for fragment assembly; de Bruijn graphs for Sequencing by Hybridization (SBH); discrete models for RNA secondary structure prediction; application of the Money Changing Problem for mass spectrometry data interpretation; modelling of genome rearrangements using strings and permutations. Time permitting, we will also have a brief look at other common applications of graphs in bioinformatics, such as graph models for protein interaction networks/metabolic networks, for protein folding, and phylogenetic trees.
The course contains an extended introduction to some basic discrete mathematics (enumeration, common sequences, induction, permutations, graphs, trees), and a part on NPcompleteness.
SUGGESTED BOOKS:
PREREQUISITES: Course Algorithms for Bioinformatics (2nd year)
EXAM: Oral exam, with a written midterm
No.  Date  Topic  Slides  Supporting material or chapters in books, comments 

1  Wed, 1/10/2014  Organisation of course; Introduction.  Organisation, Introduction 

2  Tue, 6/10/2014  Combinatorics  Fundamental counting principles 1: sum rule, product rule, bijection rule; Binomial coefficients: definition, basic recursion, some basic laws.  Aigner 1.1, 1.4; SteinDrysdaleBogart 1.1,1.2,1.3  
3  Tue, 21/10/2014  Combinatorics  Fundamental counting principles 2: double counting, pidgeonhole principle.  Aigner 1.1, 1.6  
4  Wed, 22/10/2014  Modular arithmetic; Strings, counting strings.  Aigner 12.1; SteinDrysdaleBogart 2.1; SetubalMeidanis 2.1  
5  Tue, 28/10/2014  Graphs.  Aigner 6.1; SteinDrysdaleBogart 6.1; SetubalMeidanis 2.2; Exercises (Lectures 25). 

6  Wed, 29/10/2014  Fragment Assembly (1): models.  lectures 6, 7: Fragment Assembly (print version) 
SetubalMeidanis 4.1, 4.2; Update: I added one more slide with an extra definition which was missing (new slide 20), that of a collection admitting a tcontig. Here it is: extra slide, just add it by hand on on p. 20 of your printouts. 
7  Tue, 04/11/2014  Fragment Assembly (2): models (cont.)  SetubalMeidanis 4.1, 4.2  
8  Wed, 05/11/2014  Fragment Assembly (3): greedy algorithm.  lectures 8, 9: Greedy Algorithm (print version) 
SetubalMeidanis 4.3; Here is a list of differences between these slides and the handout I gave you in class: 1. p.5: in the inductive definition, the base is with a path of length 0 (not 1) 2. p.6: 3rd line from bottom: superstrings (not substrings) 3. p.16: added "for X=n" at the beginning of last sentence, and the name "inverse Ackermann function" in the footnote. 4. p.17 (Analysis) is new, see extra slide. 5. p.18: replaced "F" by "F = n" in last line 
9  Tue, 11/11/2014  Fragment Assembly (4): More on the greedy algorithm.  SetubalMeidanis 4.3 Exercises on Fragment Assembly. 

10  Wed, 12/11/2014  Discussion of exercises on discrete maths and fragment assembly.  Solution to exercise 5 of sheet 1 (discrete maths) here.  
  Wed, 19/11/2014  Midterm exam (Prova intermedia)  2 hours  We start at 10.30, as usual. Please bring along identification (matricola) with photo. Use of notes, books, or calculators not allowed. Risultati prova intermedia: exam results. 

11  Wed, 26/11/2014  Discussion of midterm exam.  
12  Tue, 2/12/2014  De Bruijn graphs for DNA Sequencing (1): Introduction, Sequencing by Hybridization (SBH).  lectures 12, 13: De Bruijn Graphs for DNA Sequencing 1 (print version). Attention: On p. 16 TGG is missing from set S! 
Jones & Pevzner 8.68.8; Primer on DeBruijn graphs: 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 (which we will need for Lecture 15). 
13  Thu, 4/12/2014  De Bruijn graphs for DNA sequencing (2): Euler tours and Euler paths, Eulerian graphs (directed and undirected), fragment assembly via de Bruijn graphs.  
14  Tue, 9/12/2014  De Bruijn graphs for DNA sequencing (3): fragment assembly of circular sequences, comparison of different approaches (Hamiltonian cycle, Euler cycle, different values of k), handling of errors with de Bruijn graph approach.  lectures 14, 15: De Bruijn Graphs for DNA Sequencing 2 (print version) 

15  Wed, 10/12/2014  De Bruijn graphs for SBH (4): de Bruijn sequences.  See notes from class. The card trick I showed you is explained here: De Bruijn card trick, by Richard Anstee, University of British Columbia, Vancouver, Canada. Note that we only did the part of computing the first card (but, as is explained here, you can also compute the other four; or indeed, all the following ones...)  
  Mon, 15/12/2014  Repetition of midterm exam.  9:00  11:30, Aula L, Ca' Vignal, 2, 1st floor, left. Exam results.  
16  Tue, 16/12/2014  NPcompleteness (1)  lectures 16, 17: NPcompletness (print version) 

17  Wed, 17/12/2014  NPcompleteness (2)  
18  Wed, 14/1/2015  Phylogenetic trees (1): different types of phylogenetic trees, number of phylogenetic trees, different types of input data  lectures 18, 19: Phylogenetic Trees 1 (print version) 
see also class notes for some more background on trees 
19  Mon, 19/1/2015  Phylogenetic trees (2): distance data, path metric of a tree, when does a "good" tree exist?  
20  Tue, 20/1/2015  Phylogenetic trees (3): character data, Perfect Phylogeny, Maximum Parsimony  Phylogenetic Trees 2 (print version) 

21  Wed, 21/1/2015  Summary  Summary (print version) 