Bioinformatic Algorithms, UNIL 2024

Instructors: Prof. Christophe Dessimoz (CD) & Prof. David Gfeller (DG)
Assistants: Dr. Irene Julca, Dr. Alex Warwick Vesztrocy, Daniel Tadros
Location: Amphipole 336

19h lecture, 20h practical, 20h personal work (4 ECTS for MSc / 3 ECTS for PhD)

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, for-loops, 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): https://moodle.unil.ch/course/view.php?id=30087

 
Date

Lecture
Amphipole 336

Lecturer

Practical
Amphipole 336

27 Feb 2024 9.00-12.00

Introduction. How computers work; fundamentals of algorithm and complexity theory.

CD

Worksheet 1: Setting up environment, basic algorithm.

5 Mar 2024 9.00-12.00

Exact sequence matching I: read mapping, indexing

CD

Answer questions, discuss solutions.

12 Mar 2024 9.00-12.00

Exact sequence matching II: hashing, edit distances.

CD

Worksheet 2: Binary search and exact string matching; genomic signatures

19 Mar 2024 9.00-12.00

Approximate sequence matching: dynamic programming

CD

Answer questions, discuss solutions.

26 Mar 2024 9.00-12.00

Alignment significance: permutation test, parameter estimation

CD

Worksheet 3: Sequence alignment with dynamic programming

Easter break

9 Apr 2024 9.00-12.00

Networks I: Introduction to different types of networks. Graph representation and data structure. Graph and tree traversals.

DG

Answer questions, discuss solutions.

16 Apr 2024 9.00-12.00

Networks II: Clustering.

DG

Worksheet 4: Networks, Dijkstra's algorithm, viewing networks with cytoscape

23 Apr 2024 9.00-12.00

Networks III: Neural networks.

DG

Answer questions, discuss solutions.

30 Apr 2024 9.00-12.00

Network IV: Convolutional neural networks.

DG

Worksheet 5: Neuronal network to predict transmembrane residues in a protein

7 May 2024 9.00-12.00

Cross-validation, avoiding overfitting

DG

Worksheet 5: discuss solutions

14 May 2024 9.00-12.00

Hidden Markov models. Forward-backward algorithm.

CD

Worksheet 6: TBD

21 May 2024 9.00-12.00

Minimizers and Min-Hashing

CD

Answer questions, discuss solutions

28 May 2024 9.00-12.00

Conclusion. Review key ideas, next steps, feedback.

CD

Answer questions, discuss solutions