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 @ inria.fr 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 @ inria.fr and blerina.sinaimeri @ inria.fr. Here is the list of the papers chosen so far.