Modelli Biologici Discreti / Discrete Biological Models
(a.a. 2014/2015)

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


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)

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, integer-valued 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 NP-completeness.


PREREQUISITES: Course Algorithms for Bioinformatics (2nd year)

EXAM: Oral exam, with a written midterm


No. Date Topic Slides Supporting material or chapters in books,
1 Wed, 1/10/2014 Organisation of course; Introduction. Organisation,
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; Stein-Drysdale-Bogart 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; Stein-Drysdale-Bogart 2.1; Setubal-Meidanis 2.1
5 Tue, 28/10/2014 Graphs.   Aigner 6.1; Stein-Drysdale-Bogart 6.1; Setubal-Meidanis 2.2;
Exercises (Lectures 2-5).
6 Wed, 29/10/2014 Fragment Assembly (1): models. lectures 6, 7:
Fragment Assembly
(print version)
Setubal-Meidanis 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 t-contig. 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.)   Setubal-Meidanis 4.1, 4.2
8 Wed, 05/11/2014 Fragment Assembly (3): greedy algorithm. lectures 8, 9:
Greedy Algorithm
(print version)
Setubal-Meidanis 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.   Setubal-Meidanis 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.6-8.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 NP-completeness (1) lectures 16, 17:
(print version)
17 Wed, 17/12/2014 NP-completeness (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)