Modelli Biologici Discreti / Discrete Biological Models

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

News:

Primo appello (11/2/15): Tutti gli orali avranno luogo lun. 9/2/15 & mar. 10/2/15 (solo se necessario, anche 11/2/15). Arriverà una mail con la comunicazione quando sarà il vostro orale. Se il tuo nome non c'é nella lista che abbiamo fatto in classe durante l'ultima lezione (21/1/15), ma vuoi dare l'esame in questo appello, allora scrivimi una mail. Attenzione, vi dovete anche iscrivere all'appello!
Ulteriore ricevimento mercoledì prossimo (28/1/15): 8:30-10:30.
Come annunciato in classe, no ricevimento nel periodo 2-20 Feb., per motivi di missioni ed esami.
Allora i prossimi ricevimenti sono: merc. 28/1/15 8:30-10:30, giov. 29/1/15 8:30-10:30, e (solo su richiesta!): ven. 20/2/15, 8:30-10:30.
Se volete venire in uno dei ricevimenti, mandatemi una mail primo possibile, per poter gestirli meglio.
Pagine web aggiornate, tutti i slides sono disponibili. Se c'è qualche problema fatemi sapere via mail!
Results of repetition exam (15 Dec. 2014) here: Exam results.

Old News:

The written exam on Monday (repetition) 15 Dec will take place in aula L (Ca' Vignal 2, first floor, to the left), from 9 until 11.30.
The supplementary material for the article on de Bruijn graphs (Lecture 15) to be found here.
Risultati prova intermedia qui. Si possono visionare i compiti nel mio studio oppure dopo le lezioni. Vi ho anche preparato le soluzioni per tutti gli esercizi del compito. Chi non c'era nell'ultima lezione, le può prendere direttamente da me.
Please read the article on de Bruijn graphs that I distributed (see here), for next time (Tue 2 Dec).
È arrivato il libro in biblioteca "Martin Aigner: Discrete Mathematics" su cui era basato la parte di matematica discreta, in 3 copie, prestabili per 7 gg.
Come annunciato in aula, la lezione del 3 Dic (mercoledì) è stata spostata al giorno successivo, stesso orario, Laboratorio Alfa (giovedi' 4/12/14, 10:30 - 13:30), causa assemblea degli studenti.
Note that there was a typo (error) in ex. 5 the first group of exercises (those on discrete maths) that I put on the webpage (now corrected). In the lecture on 22 Oct., we wrote the exercise correctly. If you attempted to solve the exercise, using the list on the webpage, you should have noticed the error. I now put the full solution here, just to be sure: Solution to exercise 5 of sheet 1 (discrete maths) here. This is the only exercise that we didn't solve together in class.
Il ricevimento della settimana 17-21 nov. 2014 è stato spostato a lunedì, ore 11-13 (invece di giovedì), per dare la possibilità agli studenti di fare ultime domande sugli argomenti della prova intermedia (mercoledì 19 nov).
Prova intermedia: mercoledì 19 nov. 2014, dalle 10:30 in poi (2 ore), aula C. No appunti, no libri, no calcolatrici.
On Dec 3, there will be no lecture because of the "Assemblea Generale degli Studenti".

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

SUGGESTED BOOKS:

On bioinformatics:

João Setubal, João Meidanis: Introduction to Computational Molecular Biology (1997). This is my main reference.
Dan Gusfield: Algorithms on Strings, Trees, and Sequences (1997).
Neil C. Jones and Pavel A. Pevzner: An Introduction to Bioinformatics Algorithms (2004).

On discrete mathematics:

Martin Aigner: Discrete Mathematics (2007). This is a very nice book on discrete mathematics, and my main reference for that part of the course. What we do is also described in any other book on discrete mathematics.
Cliff Stein, Scot Drysdale, and Ken Bogart: Discrete Mathematics for Computer Scientists (2010). Nice book with lots of explanations and lots of examples and problems.

On algorithms:

Cormen, Leiserson, Rivest (& Stein): Introduction to Algorithms (different editions, 1990-onwards). This is the "bible" on algorithms. Always good to have a look.

PREREQUISITES: Course Algorithms for Bioinformatics (2nd year)

EXAM: Oral exam, with a written midterm

Lectures

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; 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: NP-completness (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)

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

Lectures

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