Table of Contents
Algorithmics and bioinformatics (26h, 3 ECTS)Coordination: Philippe Gambette (LIGM, Univ. Paris-Est Marne-la-Vallée). LecturersThe lecturers are researchers in the Algorithmics for Bioinformatics group at LIGM (Univ. Gustave Eiffel at Marne-la-Vallée).
Practical informationLanguageLectures will be given in English. LocationThe lectures will take place at ENS Paris-Saclay. Motivations and main objectivesThe objective of this course is to study the algorithmic approaches used in bioinformatics. The topics covered in 2022-2023 include scaffolding, reversal and transposition distances, scaffold filling and phylogenetics. Short descriptionA total of 26 hours of lectures and exercise sessions, from September 21st to November 9th (to be confirmed):
Lecture notes* Gregory Kucherov: * Philippe Gambette:
Evaluation / examsThe evaluation of the students will consist in a written exam (coefficient 1), as well as a coding project (optional, coefficient 1). Written examThe written exam will be on November 22nd. The exercises will be given in English, and you can write your answers in English or in French. You'll be authorized to have your lecture notes with you (but no computer, cellphone, etc.) Coding projectStudents will also be in charge of programming a solution to a problem occurring in bioinformatic algorithms, in Python. This work will be optional and will only be taken into account if it increases the global mark for the course. For year 2022, the coding project consists in programming an algorithm to solve the OTCM or the OTDE problem, namely to find the optimal order on the leaves of a phylogenetic tree given as input such that the tree is planar and the order is as close as possible to the optimal order, either counting the number of crossings (OTCM) or the number of leaves to delete to get no crossings (OTDE). More details in this paper and in this video.
The project will be coded in Python, in only one Python file, using only the following libraries: argparse, glob, itertools, numpy, os, pathlib, re, sys and time. Students wanting to use other libraries, or who have any question about the coding project, are invited to contact Philippe Gambette (
This Python script is supposed to take as input a text file in UTF8 encoding, called This code should have added value compared with the code available in this GitHub repository, which provides examples of input files, for example:
The project will be evaluated taking into account the correctness of the code, its speed, its readability (quality of comments in particular) as well as the quantity of code written personally and the respect of intellectual property.
The deadline for this coding project task will be November By default this project will be done individually, if you want to make a group project, please contact me by email to describe which variant of the algorithm you plan to code, and the composition of the group, so that I can confirm if there is enough work for a group project. So far, the following projects have been received (please contact me if you sent me your project and your name does not appear below 2 days after you sent it, your email may be in my spam folder):
Schedule
Prerequisites
Related courses
Bibliography
|