Network Algorithms for Molecular Biology

Lecturers: Blerina Sinaimeri & Marie-France Sagot, Inria European Team Erable & CNRS-UCBL Team Baobab

Graphs are intensively used in biology, either as interesting structures to model some types of data, for instance those produced by the new sequencing technologies, or as direct models of biological entities or processes, such as regulation or metabolism. In the latter case, the graphs are called networks which can thus be regulatory or metabolic, or else integrate further data of different types (cell signaling, protein-protein interaction, etc). Graphs have also been more recently suggested as better models than trees for the evolution of at least certain types of organisms, such as bacteria. We thus speak of phylogenetic networks instead of phylogenetic trees.

The graph algorithmic problems raised by any such cases may be revisits of old problems (such as cycle or path enumeration) that call for more efficient resolutions given the size of some of the biological graphs, or introduce constraints that can make the originally pure algorithmic problem either easier or harder to address. Often however, a biological question may lead to completely new algorithmic problems, or call for new, more elaborate models. One example of this are directed hypergraphs as introduced by Giorgio Ausiello. These are an extension of the definition initially proposed by Claude Berge.

The purpose of this 24-hours course on Network Algorithms for Biological Networks is to introduce all the above aspects by means of some well-chosen examples which will be explored in some depth.

The planning for the course for the period 2016-2017 is as follows:

Date Topic
Sep 15, 2016 Presentation of the course and general introduction to biology
Sep 22, 2016 General overview of networks (graphs) in biology & associated algorithms
Oct 6, 2016 General introduction to enumeration algorithms
Oct 13, 2016 Enumeration algorithms
Oct 20, 2016 Introduction to (de novo) assembly
Nov 3, 2016 Enumeration problems in RNA-seq data
Nov 10, 2016 Algorithmic issues in (co)phylogenetic analysis
Nov 17, 2016 Algorithmic issues in (co)phylogenetic analysis
Nov 24, 2016 Wolbachia infection and cytoplasmic incompatibility
Dec 8, 2016 Finding coloured motifs in networks

The slides of each course will be available one or two days before (for this, just click on the title of the course). For those who want to go further, some bibliographic references will be indicated in the last slide of each course.

The Homework should be sent to blerina.sinaimeri @ before December 20. You can find the exercises of the homework here.

Some open problems can be found here.

The papers for the final exam are available here. The choice of paper to present must be indicated by email by Dec 20 at the latest to marie-france.sagot @ and blerina.sinaimeri @ Here is the list of the papers chosen so far.