Action Spécifique
Modélisation et Algorithmique des Structures d'ARN
dans le cadre du réseau Bioinformatique STIC-CNRS
(2002-2003)






Sommaire :



Responsables

Alain Denise, LRI Orsay, Université Paris-Sud.                    Alain.Denise@lri.fr
Serge Dulucq, LaBRI, Université Bordeaux I.                         Serge.Dulucq@labri.fr

 Rapport final (décembre 2003)

Participants

Equipes impliquées   :
  • BBE, UMR 5558 (SdV et STIC), Lyon : Marie-France Sagot, Julien Allali (IGM Marne-la-Vallée), Marina Zelwer.
  • *IRIN, UPRESA 2157, Nantes : Guillaume Blin, Guillaume Fertin, Irena Rusu.
  • LaBRI, UMR 5800 (STIC), Bordeaux : Serge Dulucq, Isabelle Dutour, Pascal Ferraro, Claire Herrbach (et LRI), Laurent Tichit.
  • LaMI, UMR 8042 (STIC), Evry : Fariza Tahi, Stefan Engelen.
  • LIFL, UMR 8022 (STIC), Lille : Hélène Touzet, Olivier Perriquet.
  • *LIX, UMR 7650 (STIC), Palaiseau : Jean-Marc Steyaert, Behshad Behzadi, Jérôme Waldispühl.
  • LRI, UMR 8623 (STIC), Orsay : Patrick Amar, Alain Denise, Christine Froidevaux, Jean-Paul Forest, Claire Herrbach (et LaBRI),Yann Ponty, Romain Rivière, Stéphane Vialette.
  • *Autres participants : Dominique Barth (PRISM Versailles), Michel Termier (IGM Orsay).

  • (*équipes intégrées à l'action après le démarrage.)
     

    Réunions du groupe

    Thèmes scientifiques

    La plupart des gènes d'un organisme s'expriment sous forme de protéines ; cependant, pour certains d'entre eux, le produit final n'est pas une protéine mais une molécule d'ARN. Ces ARN ont des fonctions structurelles ou enzymatiques importantes dans la cellule. Une molécule d'ARN est constituée d'une succession de nucléotides A, C, G et U. A ce titre, elle est comparable à une molécule d'ADN. Cependant, à la différence de cette dernière, la molécule d'ARN adopte dans l'espace une conformation complexe qui dépend des interactions physico-chimiques de ses constituants. C'est cette structure qui détermine la fonction de la molécule dans la cellule. Or, excepté quelques rares cas de molécules cristallisées en laboratoire, on ne connaît généralement d'une structure d'ARN que sa séquence primaire, c'est-à-dire la suite linéaire de ses nucléotides.

    Le problème de la prédiction de la structure d'un ARN à partir de sa séquence est réputé difficile. Les algorithmes existants à ce jour se contentent de déterminer la structure secondaire de la molécule, qui est une représentation simplifiée (ne tenant compte que de certaines interactions) de sa véritable conformation. De plus, les méthodes de prédiction qui utilisent comme seule information la séquence primaire donnent des résultats médiocres. Pour améliorer la prédiction, d'autres méthodes prennent en compte des informations supplémentaires. En particulier, les méthodes basées sur la comparaison de plusieurs molécules d'ARN apparaissent comme prometteuses. Par exemple, il peut s'agir de déterminer la structure commune à plusieurs séquences dont on suppose qu'elles ont des conformations similaires. De ce fait, il existe un lien très fort entre la prédiction et la comparaison des structures secondaires. Par ailleurs, la problématique de la comparaison a des applications importantes dépassant le seul cadre de la prédiction, par exemple dans le domaine de la phylogénie. Sur ce plan, on pourra noter que l'algorithmique de la comparaison de structures est un sujet bien plus complexe que celui de la comparaison de séquences, faisant notamment appel à des techniques et des outils de modélisation plus fins. Notre groupe s'intéresse aux deux thématiques de la prédiction et de la comparaison, tout d'abord parce que l'une enrichit l'autre comme on l'a vu, mais aussi parce qu'elles font appel aux mêmes concepts théoriques.

    Logiciels développés par des membres de l'action :

    Quelques publications des membres de l'action :

    Michaël Bekaert, Laure Bidou, Alain Denise, Guillemette Duchateau-Nguyen, Jean-Paul Forest, Christine Froidevaux, Isabelle Hatin, Jean-Pierre Rousset and Michel Termier. Towards a computational model for eukaryotic -1 frameshifting sites. Bioinformatics 19 (2003) 327-335.

    Alain Denise, Yann Ponty and Michel Termier. Random generation of structured genomic sequences. Poster to be presented at RECOMB 2003, April 2003, Berlin.

    Serge Dulucq and Laurent Tichit. À propos de la comparaison de structures secondaires d'ARN.Actes du Colloque JOBIM 2001 Biologie, Informatique Mathématiques, June 2001, Toulouse, 125-134.

    Serge Dulucq and Laurent Tichit. RNA secondary structure comparison: exact analysis of the Zhang-Shasha tree edit algorithm. Theoretical Computer Science, 2003, to appear.

    Serge Dulucq and Hélène Touzet. Analysis of tree edit distance algorithms. Fourteenth Annual Symposium on Combinatorial Pattern Matching (CPM 2003), Mexico, 2003, Lecture Notes in Computer Science, to appear.

    Olivier Perriquet, Hélène Touzet and Max Dauchet. Finding the common structure shared by two homologous RNAs. Bioinformatics 19, pp 108-116, 2003.

    Fariza Tahi, Manolo Gouy and Mireille Régnier. Automatic RNA secondary structure prediction with a comparative approach. Computers and Chemistry, vol. 26, no 5, 2002. pages 521-530.

    Fariza Tahi, Stefan Engelen and Mireille Régnier. A fast algorithm for RNA secondary structure prediction including pseudoknots. 3rd IEEE Symposium on Bioinformatics and Bioengineering (BIBE 2003), March 10-12 2003, Bethesda, Maryland. In IEEE Computer Society proceedings, pages 11-17.

    Hélène Touzet. Tree edit distance with gaps. Information Processing Letters 85 (3), pp 123 - 129, 2003.

    Jérôme Waldispühl, Behshad Behzadi and Jean-Marc Steyaert. An Approximate Matching Algorithm for Finding (Sub-)Optimal Sequences in S-attributed Grammars. Proc. ECCB 2002, Bioinformatics 18 (2002) 250-259.