|Title of course:|| Modelli Biologici Discreti/
Discrete Biological Models
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)
||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|
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:
|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:
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
|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:
|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
|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