Présentation ↑
L'École
de Printemps d'Informatique Théorique est une institution dans
le domaine de l'informatique théorique en France.
L'École s'est développée sous la direction de Maurice Nivat en 1973.
Durant ses 40 ans d'existence, elle a couvert un large spectre des thèmes
porteurs en informatique théorique et elle représente maintenant le lieu
de rencontre par excellence pour les nouvelles générations de chercheurs
du domaine.
Cette année, EPIT 2014 aura lieu sur l'Île d'Oléron, du 11 au 16 mai. L'algorithmique pour la bioinformatique sera mise en avant. La rapidité et l'ampleur des évolutions technologiques d'acquisition de données dans les domaines de la biologie moléculaire et cellulaire, notamment de la génomique et de la post-génomique, suscitent un fort besoin méthodologique en informatique et en mathématiques appliquées, aussi bien sous l'angle de l'intégration des données que sous ceux de leur analyse et du développement de nouveaux algorithmes et modèles. Cette école se propose d'en aborder certains aspects à fort impact.
Programme ↑
| Dimanche 11 mai |
| l'après-midi | accueil des participants à la Gare de La Rochelle et départ en navette pour l'Île d'Oléron |
| 17h15 | départ du bus de la gare SNCF de La Rochelle pour l'Île d'Oléron |
| Lundi 12 mai |
| 9h-10h30, 11h-12h30 | cours 1 - Alain Denise
Combinatoire et algorithmique de l'ARN (1)Les molécules d'ARN, naturellement encodées par des séquences sur l'alphabet {A,C,G,U}, se replient in vivo pour adopter une grande diversité de conformations, déterminant fortement leur fonction. Ce mécanisme du repliement est gouverné par l'appariement d'un ensemble de positions à travers la formation de liaisons hydrogènes. Il en découle une abstraction discrète de la conformation d'une molécule, la structure secondaire, qui peut être prédite en temps polynomial, et permet une représentation simplifiée, mais fidèle, de la structure d'ARN. Ce cours alternera deux interventions illustrant, dans le contexte du repliement d'ARN, l'utilisation des outils de la combinatoire énumérative et analytique pour la conception d'algorithmes de programmation dynamique. Dans une première partie, nous présenterons brièvement les notions de base sur l'ARN et nous décrirons quelques uns des principaux problèmes bioinformatiques et algorithmiques liés à l'analyse des séquences et des structures d'ARN. Nous nous attacherons ensuite à la représentation des séquences et structures d'ARN par des spécifications combinatoires. Nous focaliserons une partie de l'exposé sur l'étude et la génération de séquences et structures aléatoires. Nous illustrerons ainsi comment la combinatoire énumérative et la combinatoire analytique interviennent dans l'étude des propriétés des séquences, des structures, et des algorithmes qui les traitent. [... voir cours 2...] |
| 14h-15h30, 16h-17h30 | cours 2 - Yann Ponty
Combinatoire et algorithmique de l'ARN (2)Les molécules d'ARN, naturellement encodées par des séquences sur l'alphabet {A,C,G,U}, se replient in vivo pour adopter une grande diversité de conformations, déterminant fortement leur fonction. Ce mécanisme du repliement est gouverné par l'appariement d'un ensemble de positions à travers la formation de liaisons hydrogènes. Il en découle une abstraction discrète de la conformation d'une molécule, la structure secondaire, qui peut être prédite en temps polynomial, et permet une représentation simplifiée, mais fidèle, de la structure d'ARN. Ce cours alternera deux interventions illustrant, dans le contexte du repliement d'ARN, l'utilisation des outils de la combinatoire énumérative et analytique pour la conception d'algorithmes de programmation dynamique. [... voir cours 1...] Au sein d'une deuxième partie, nous expliquerons comment ces spécifications peuvent être transformées, de façon générique, en des schémas récursifs sous-jacents à des algorithmes de programmation dynamique pour diverses applications. Parmi celles-ci, on pourra noter la prédiction de structure maximisant le nombre d'appariements, minimisant une notion d'énergie libre, ou bien permettant le calcul de la fonction de partition, une quantité essentielle en physique statistique. Nous montrerons ensuite comment cette analogie peut être exploitée afin de dériver des familles d'algorithmes efficaces pour l'analyse, dans des séquences, de propriétés additives sur les séquences. Nous conclurons avec une série de problème ouverts parmi lesquels le design d'ARN, i.e. la conception d'une séquence se repliant d'une façon prédéterminée et dont le statut au regard de la théorie de la complexité reste alors inconnu. |
| Mardi 13 mai |
| 9h-10h30, 11h-12h30 | cours 3 - Elisabeth Remy
Analyse qualitative de la dynamique des réseaux de régulation via la modélisation logiqueLa modélisation des réseaux de régulation par un formalisme discret permet une analyse qualitative de la dynamique du réseau étudié et de ses propriétés. Malgré la simplicité des modèles Booléens, nous sommes très vite confrontés à la taille de l'espace des phases, qui croit exponentiellement avec le nombre d'éléments (de gènes) considérés, et qui devient difficile, voire impossible, à générer. Pour faire face à ce problème, nous développons des méthodes et outils d'analyse (réduction de modèles, analyse de motifs dans le graphe de régulation, ...) que nous mettons en oeuvre pour comprendre et accéder aux propriétés des réseaux étudiés. Après une présentation de la modélisation logique, de ses propriétés, nous mettrons en application cette méthodologie à travers l'étude d'un modèle logique construit dans le but de mieux comprendre le rôle de la voie RB/E2F dans la progression du cancer de la vessie.
vidéo 1  ,
vidéo 2 ,
vidéo 3 ,
vidéo 4
|
| 14h-15h30, 16h-17h30 | cours 4 - Celine Scornavacca
Introduction à la phylogénétique et à la phylogénomiqueDans ce cours, je vais commencer par introduire la thématique de la reconstruction de relations évolutives entre espèces à partir de données moléculaires et morphologiques (la phylogénétique), et ses enjeux. Ensuite, je vais présenter les objets combinatoires utilisés en phylogénétique (arbres phylogénétiques, alignements de séquences etc.) et les méthodes les plus utilisées pour reconstruire des arbres phylogénétiques, d'abord dans un contexte purement phylogénétique et ensuite dans un contexte phylogénomique (méthodes de parcimonie, de distances, de super arbre, réconciliations arbre de gènes/arbres d'espèces etc.). A la fin du cours, le concept de réseau phylogénétique sera aussi évoqué. |
| Mercredi 14 mai |
| 9h-10h30, 11h-12h30 | cours 5 - Xiaodong Wu
The Emerging Areas of Computational Medicine: Problems, Solutions, and Research TrendsThe course will be mainly focused on radiation treatment planning (including IMRT and Rotating-shield brachytherapy) and medical image segmentation. |
| Jeudi 15 mai |
| 9h-10h30, 11h-12h30 | cours 6 - Eric Rivals
Analyse de séquençage haut débit : besoins et solutions algorithmiquesDans les sciences du vivant, l'utilisation des technologies de Séquençage à Haut Débit (SHD), aussi appelées Séquençage de Nouvelle Génération (NGS), permettent d'obtenir des données globales (à l'échelle de tout le génome, ou concernant tous les gènes ou ARN) pour étudier des questions biologiques très diverses, par exemple : quels sont les gènes activés dans telle condition ? où se situent dans le génome les régions régulatrices qui interfèrent avec telle protéine ? etc. De ce fait, les projets qui exploitent ces technologies se sont multipliés et rendent aigu le besoin d'algorithmes pour explorer, fouiller, comparer des collections de données SHD. Nous aborderons quelques problèmes algorithmiques liés à l'analyse de séquences haut-débit, tels que la correction d'erreurs de séquençage, la prédiction de variations génomiques, ou l'assemblage. Nous verrons l'articulation avec les questions d'indexation de séquences sans lesquelles de nombreux problèmes resteraient insolubles en pratique vu l'importance des volumes de données. Ainsi, ces volumes évoluent avec les technologies, et les futures recherches devront encore innover sur le versant des algorithmes tout en démontrant que les algorithmes proposés sont à même de traiter les volumes produits par les SHD, c'est-à-dire de passer à l'échelle. |
| 14h-15h30, 16h-17h30 | cours 7 - Gregory Kucherov
Full-text indexes for genomic dataIt is now a commonplace that Next-Generation Sequencing technologies produce an unprecedented amount of DNA sequence data that should be stored, accessed and processed efficiently. In this lecture, we will give a survey of indexing data structures for sequence data, both from theoretical and practical perspective. We start with the classical suffix tree data structure that remains a very popular tool in theoretical studies as well as in some practical applications. We also present two related structures ? Directed Acyclic Word Graph (DAWG) and position heap. We then present the suffix array, which is a more space-efficient structure in practice. Finally, we present a yet more compact data structure ? so-called FM-index ? based on the combinatorial Burrows-Wheeler transform. FM-index is now becoming an ubiquitous tool in many NGS-related applications that we illustrate with several examples.
vidéo 1 ,
vidéo 2 ,
vidéo 3 ,
vidéo 4 ,
vidéo 5
|
| Vendredi 16 mai |
| 9h-10h30, 11h-12h30 | cours 8 - Eric Tannier
Combinatoire des réarrangements génomiquesMacromolecules (DNA, RNA, proteins) are long sequences over small alphabets which contain informations about the functionning of the carrier organisms as well as traces of their descent, the history of individuals, populations, species, up to the deep history of life. As every lineage records its own events, the comparison of molecules with dedicated algorithms allows to decipher the information stored in these chemical strings. Models to describe and compare macromolecules (DNA, RNA, proteins) use classical combinatorial objects as sequences of letters over finite alphabets, permutations or graph matchings to decribe gene orders or trees to describe evolutionary relationships between extant organisms. This lecture is devoted to the algorithmics designed for the description and the understanding of molecular data and their evolution, with a focus on the comparison of whole genomes. |
| 14h | fin d'EPIT 2014
départ du bus pour La Rochelle (durée prévue : 1h15 environ) |
Photos ↑
Participants ↑
Localisation ↑
CAES du CNRS
La Vieille Perrotine
140, route des Allards
17310 Saint Pierre d'Oléron
Agrandir la carte
Une navette sera proposée depuis la gare SNCF de La Rochelle le dimanche 11 mai (départ de La Rochelle à 17h30) pour accéder à l'île d'Oléron,
et pour le retour à La Rochelle le vendredi 16 mai (départ du centre de la Vieille Perrotine à 14h, durée estimée à 1h15 environ).
Partenaires ↑
L'édition 2014 de l'École de Printemps d'Informatique Théorique
est organisée avec le soutien du
CNRS, de ses GDR
BiM (Bioinformatique Moléculaire)
et
IM (Informatique-Mathématique), de l'
Université
Paris-Est Marne-la-Vallée, du
Labex Bézout
d'Université Paris-Est, ainsi que des projets
Investissements d'avenir ABS4NGS et
ANR JC BIRDS SIMI2 2010.
Organisateurs ↑
Contacts : philippe.gambette@u-pem.fr, stephane.vialette@u-pem.fr.
