Algorithmics and bioinformatics (56h, 8 ECTS)

Coordination: Thomas Nowak (LMF, ENS Paris-Saclay).

• For year 2023-2024, the lecturer will be Stefan Haar (for the first part) and Matthias Fuegger & Thomas Nowak (for the second part)
• For year 2022-2023, the lecturers will be Gregory Kucherov and Philippe Gambette.
• For year 2021-2022, the lecturers were Gregory Kucherov and Philippe Gambette.
• For year 2020-2021, the lecturers were Laurent Bulteau and Mathias Weller.

Lectures will be given in English. The lectures will take place at ENS Paris-Saclay, room 1E14, on Tuesday morning from 9:30 AM to 1:30 PM, following the schedule.

The objective of this course is to study the algorithmic foundations of biological systems. The organization in 2023-2024 includes two parts, each of seven weeks. Each part is independent and gives 4 ECTS.

The first part presents discrete models for biological networks. We will study some aspects of the formal analyis of models for the dynamics of cell processes, with a focus on cell regulation and the search for attractors, aka phenotypes. After a general overview of formal modeling in biological dynamics, we will focus on boolean networks and their analysis, including the analysis via interaction graphs and temporal logics. We will then look beyond the boolean function model to include Petri nets and their unfoldings, and question the boundary between discrete and continuous models.

The second part studies biological circuit design. Using kinetic models from biochemistry as a foundation, we first show how to build circuit components like logical gates and oscillators out of biological parts. We then investigate design strategies to build biological systems with more complex behavior out of these basic building blocks. A guiding principle will be to use tested biochemical models as a foundation and to mathematically prove the desired behavior of the system in these models.

Lecture notes for the second part can be found here: https://robacon.github.io/course/

The second part will be graded based on theoretical and practical lab work only. There will be no written exam.

No previous knowledge of biology or chemistry is required. The following will be helpful, however:

• basic algorithmics and programming (we'll program in Python)
• basic graph theory definitions
• basic circuit theory (notions like NAND, NOR shouldn't scare you)
• basic probability theory
• vocabulary of ordinary differential equations

• Probabilistic Aspects of Computer Science
• Biochemical Programming
• Distributed Algorithms for Networks

• Uri Alon, An Introduction to Systems Biology, 2nd edition, CRC Press, Boca Raton, 2019.
• Bruce Alberts et al., Molecular Biology of the Cell, 7th edition, W. W. Norton & Company, New York, 2022.
• Jennifer A. N. Brophy and Christopher A. Voigt, Principles of genetic circuit design, Nature Methods 11(5):508-520, 2014.
• Alec A. Nielsen et al., Genetic circuit design automation, Science 352(6281), 2016.
• M. Omar Din et al., Synchronized cycles of bacterial lysis for in vivo delivery, Nature 536:81-85, 2017.
• Michael J. Diao, M. Omar Din, Lev Tsimring, and Jeff Hasty, Rock-paper-scissors: engineered population dynamics increase genetic stability, Science 365(6457):1045-1049, 2019.