Bioinformatic Algorithms, UNIL 2018
Instructors: Prof. Christophe Dessimoz (CD) & Prof. David Gfeller
(DG)
Assistants: Dr. David Dylus & Dr. Leonardo de Oliveira Martins
(DG)
15h lecture, 15h practical, 10h personal work (3 ECTS)
The course aims at improving the student’s programming skills by gaining a deep understanding of some of the key algorithms in bioinformatics, with a special emphasis on sequence and graph algorithms. Students will learn widely applicable concepts, such as asymptotic time complexity, binary search, suffix trees, dynamic programming, hashing, hidden Markov models, and neuronal networks.
Practicals and home assignments are essential parts of the course. The language of the course is Python, though the concepts covered in the course are applicable to all computer languages.
Assessment: 20 min oral examination
Prerequisites: The course assumes familiarity with basic programming concepts (variable and function declaration, arrays, forloops, conditional statements, etc.). Algorithms are introduced from a practical angle so the mathematical formalism is kept at a minimum.
Moodle page (for Q&A, slides, worksheets, etc): http://moodle2.unil.ch/course/view.php?id=6217
Date 
Lecture (910.25am)

Lecturer 
Practical (10.3512am)


1 March 2018 
Introduction. How computers work; fundamentals of algorithm and complexity theory. 
CD 
Worksheet 1: Setting up environment, basic algorithm. 
8 March 2018 
Exact sequence matching I: read mapping, indexing 
CD 
Answer questions, discuss solutions. 
15 March 2018 
Exact sequence matching II: hashing, edit distances. 
CD 
Worksheet 2: Binary search and exact string matching; genomic signatures 
22 March 2018 
Approximate sequence matching: dynamic programming 
CD 
Answer questions, discuss solutions. 
29 March 2018 
Alignment significance: permutation test, parameter estimation 
CD 
Worksheet 3: Sequence alignment with dynamic programming 
Easter break 

12 Apr 2018 
Networks I: Introduction to different types of networks. Graph representation and data structure. Graph and tree traversals. 
DG 
Answer questions, discuss solutions. 
19 Apr 2018 
Networks II: Clustering. 
DG 
Worksheet 4: Networks, Dijkstra's algorithm, viewing networks with cytoscape 
26 Apr 2018 
Networks III: Neural networks. 
DG 
Answer questions, discuss solutions. 
3 May 2018 
Hidden Markov models. Forwardbackward algorithm. 
CD 
Worksheet 5: Neuronal network to predict transmembrane residues in a protein 
Ascension 

17 May 2018 
Conclusion. Review key ideas, next steps, feedback. 
CD 
Answer questions, discuss solutions. 