Algorithmique, combinatoire du texte
et applications en bio-informatique

Lille, 8 et 9 décembre 2011

Les 8 et 9 décembre se tiendront à Lille les journées "Algorithmique, combinatoire du texte et applications en bio-informatique", organisées conjointement par le GDR Bio-Informatique Moléculaire et le GDR Informatique Mathématique (groupe COMATEGE, Combinatoire des mots, algorithmique du texte et du génome). Ce workshop sera jumelé à une journée thématique Analyse bio-informatique des données NGS, qui se tiendra la veille au même endroit.

Les thèmes abordés vont de la combinatoire et de l'algorithmique du texte à leurs applications à l'analyse bio-informatique des séquences biologiques. Cela inclut les sujets suivants, sans y être limité :

• combinatoire des mots, statistiques sur les mots
• algorithmique du texte, structures d'indexation
• algorithmique parallèle
• recherche, découverte et analyse de motifs et de répétitions
• analyse des données de séquençage haut-débit (génomique, RNA-seq, Chip-seq,...)
• annotation des génomes, prédiction de gènes
• haplotypes et polymorphismes
• génomique comparative
• signaux de regulation

Les exposés seront organisés par session avec des sensibilités plus informatique, mathématique, ou bio-informatique.

Informations pratiques

Le plan d'accès et le programme à télécharger

Les journées se tiendront dans l'amphithéatre Butiaux, sur le campus de l'Institut Pasteur de Lille, en centre ville. Le site est desservi par le métro (ligne 2, station Grand Palais), et est à 15 minutes à pied des gares Lille Flandres et Lille Europe. Pour l'hébergement, nous vous proposons une liste d'hôtels.

Programme

• jeudi 8 décembre
  • 9h45: Café d'accueil
  • Séquençage haut-débit
    • 10h15 – 10h50: KisSplice: de-novo calling alternative splicing events from RNA-seq data Gustavo Sacomoto, Pavlos Antonious, Kielbassa Janice, Rayan Chikhi, Raluca Uricaru, Marie-France Sagot, Pierre Peterlongo, Vincent Lacroix,
    • 10h50 – 11h25: A New Software to Filter Total RNA for Metatranscriptomic or Ribosomal RNA Analysis, Evguenia Kopylova, Laurent Noé, Hélène Touzet
    • 11h25 – 12h: Comparison of large scale metagenomic data in Tara Oceans project, Nicolas Maillet
  • 12h – 13h45: repas
  • Annotation de génomes, génomique comparative
    • 13h45 – 14h20: Décodage à longueur variable et comparaison de séquences sans alignement, Gilles Didier
    • 14h20 – 14h55: Rethinking global analyses and algorithms for comparative genomics in a functional MapReduce style, Natalia Golenetskaya, David James Sherman
    • 14h55 – 15h30: Genome Dedoubling by DCJ and Reversal, Antoine Thomas, Aida Ouangraoua, Jean-Stéphane Varré
    • 15h30 – 16h05: Classifying Protein Structures by Means of Ant Motifs, Rabie Saidi, Wajdi Dhifli, Mondher Maddouri, Engelbert Mephu Nguifo
  • 16h05 – 16h30: pause
  • Stringologie (I)
    • 16h30 – 17h30: Keynote Talk, Finite Automata for Bioinformatics, Jan Holub, Université de Prague
    • 17h30 – 18h05: On-line Construction of Position Heaps, Gregory Kucherov

• vendredi 9 décembre
  • Annotation de génomes
    • 9h – 10h: Keynote Talk, Modeling gene regulatory complexes using both TF-DNA and TF-TF interactions, Esko Ukkonen, Université de Helsinki
  • Stringologie (II)
    • 10h – 10h35: Pseudo-minimisation linéaire de l’automate de Aho-Corasick, Omar Ait Mous, Frédérique Bassino, Cyril Nicaud
    • 10h35 – 11h: pause
    • 11h – 11h35: Recherche approximative de motifs dans des mots de taille fixe, Tuan Tu Tran, Mathieu Giraud, Jean-Stéphane Varré
    • 11h35 – 12h10: Efficient comparison of sets of intervals with NC-lists, Yufei Luo, Matthias Zytnicki, Hadi Quesneville
  • 12h10 – 14h: repas
  • 14h – 14h30: open discussion
    • 14h30 – 15h30: Keynote Talk, 2001–2010: Ten years of exact string matching algorithms, Thierry Lecroq, LITIS EA 4108, Université de Rouen
    • 15h30 – 16h05: Maximal Exponent repeats in Overlap-free strings, Golnaz Badkobeh, Maxime Crochemore and Chalita Toopsuwan

Dates importantes

• 4 novembre 13 novembre : date limite pour la soumission d'un résumé
• 14 novembre 17 novembre : diffusion du programme
• 24 novembre : date limite d'inscription

Inscriptions

Les inscriptions sont closes. Les retardataires peuvent contacter Helene.Touzet @ lifl.fr.

Instructions pour soumettre un résumé

Si vous souhaitez présenter vos travaux, envoyez un résumé de deux pages au format PDF, en français ou en anglais, incluant titre, auteurs et affiliations, description des recherches et bibliographie.

Les soumissions se font via le serveur easychair.

Pour les doctorants

La participation à ces journées peut éventuellement être validée comme formation par votre École Doctorale. Merci de vous renseigner auprès de votre École Doctorale, puis de contacter à ce sujet Samuel.Blanquart @ inria.fr.

Comité scientifique

• Samuel Blanquart, LIFL, CNRS, Université Lille 1, INRIA Lille
• Guillaume Blin, IGM, Marne-La-Vallée
• Mathieu Giraud, LIFL, CNRS, Université Lille 1, INRIA Lille
• David Hot, Institut Pasteur de Lille
• Thierry Lecroq, LITIS, Rouen
• Laurent Noé, LIFL, CNRS, Université Lille 1, INRIA Lille
• Pierre Peterlongo, INRIA, Rennes
• Éric Rivals, LIRMM, Montpellier
• Mikael Salson, LIFL, CNRS, Université Lille 1, INRIA Lille
• Hélène Touzet, LIFL, CNRS, Université Lille 1, INRIA Lille

Précédentes éditions

Cette réunion fait suite aux rencontres suivantes, communes aux GDR BIM et IM:

• Marne-La-Vallée, septembre 2007
• Montpellier, janvier 2010
• Rennes, janvier 2011

Contact

Pour toute information sur ces journées, ou bien en cas de problème avec le serveur easychair ou avec le formulaire d'inscription, merci de contacter Mathieu.Giraud @ lifl.fr.

Résumés des présentations invitées

• Modeling gene regulatory complexes using both TF-DNA and TF-TF interactions, Esko Ukkonen, Université de Helsinki, Department of Computer Science
  Transcription factors (TFs) not only bind to DNA but also to each other. The individual interactions between TFs are often weak. However, the complexes formed by both TF-DNA and TF-TF interactions are much more stable than those based on similar TF-DNA interactions alone. Thus, the dimerization mediated by DNA gives a much richer regulatory machinery that has a potentially stronger capability to explain the regulation of gene expression. The talk will describe recent developments in modeling and predicting such regulatory complexes, using alignment-based and alignment-free techniques and data from high-throughput SELEX experiments, and applying this to explain observed binding patterns in DNA. (Joint work with J. Taipale, T. Kivioja, P. Rastas, A. Jolma and J. Toivonen)
• Finite Automata for Bioinformatics, Jan Holub, Université de Prague
  The finite automata are well developed tools used in many areas of computer science. We show several approaches useful in bioinformatics: deterministic finite automaton, deterministic simulation of nondeterministic finite automaton, finite automaton as a model of computation, and compositions of finite automata solutions.
• 2001–2010: Ten years of exact string matching algorithms, Thierry Lecroq, LITIS EA 4108, Université de Rouen
  The online exact string matching problem consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry.
  In the last decade more than 50 new algorithms have been proposed for the problem, which add up to a wide set of (almost 40) algorithms presented before 2000. We will review the most efficient string matching algorithms presented in the last decade in order to bring order among the dozens of articles published in this area.
  We also performed comparisons between 85 exact string matching algorithms with 12 text of different types. We will present which algorithms are the most efficient depending on the alphabet size and the pattern length. (Joint work with Simone Faro)