Learning outcomes

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) master 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 or metabolic networks, for protein folding, and phylogenetic trees.

The course contains an extended introduction to fundamental concepts of discrete mathematics (enumeration, common sequences, induction, permutations, graphs, trees), and a part on NP-completeness.

Prerequisites: Course Algorithms for Bioinformatics (2nd year)

Examination Methods

Oral exam, with a written midterm exam.