Responsables de l'AS :
Alain Denise et Serge Dulucq
15 décembre 2003
L'Action Spécifique ``Modélisation et Algorithmique des Structures d'ARN'' émane du RTP 41 ``Bioinformatique''. Elle a été lancée à l'automne 2002 et financée à hauteur de 30500 euros. Les 5 équipes STIC participantes d'origine ont été rejointes quelques mois après par deux autres équipes et quelques chercheurs isolés.
Le but affiché de cette action était de fédérer les équipes STIC travaillant sur les problèmes de modélisation combinatoire et d'algorithmique liés à l'étude bioinformatique des molécules d'ARN afin de créer des synergies et aboutir à des recherches communes. Pour cela, deux réunions plénières ont été tenues et des visites inter-laboratoires ont été effectuées. Elles ont favorisé l'émergence de nouvelles collaborations au sein du groupe, et la consolidation des collaborations déjà existantes.
Nous présentons ici le rapport des activités scientifiques de l'action
(pages ![[*]](/usr/share/latex2html/icons/crossref.png){kind=icon}
à ), suivi du bilan
financier (page ) puis d'une annexe technique comprenant
notamment les références des publications du groupe (pages
à ). Un certain nombre de
ces publications sont accessibles sur la page web de l'action :
http://www.lri.fr/1#1denise/ArnStic.
Selon le dogme central de la biologie moléculaire, l'information génétique contenue dans l'ADN est transcrite en ARN messagers, puis traduite en protéines. Celles-ci sont les acteurs majoritaires du fonctionnement de la cellule. Dans ce schéma, l'ARN ne joue qu'un rôle d'intérmédiaire. Toutefois, on sait que certains ARN ne sont pas traduits en protéines : ils ont un rôle fonctionnel en eux-mêmes. C'est le cas par exemple des ARN ribosomiques et des ARN de transfert qui jouent un rôle essentiel dans le processus de traduction. Depuis quelques années, on découvre que beaucoup plus d'ARN qu'on ne le croyait possèdent des propriétés enzymatiques, et donc jouent un rôle en tant que tels dans l'activité cellulaire [7]. Par ailleurs, on a montré que certains ARN messagers eux-mêmes ont, du fait de leur structure, un effet sur la régulation de l'expression des protéines qu'ils codent [27]. L'étude des molécules d'ARN, dans leurs aspects structurels, fonctionnels et dynamiques fait maintenant partie des problèmes phares dans le domaine de la bioinformatique.
Les équipes engagées dans l'action spécifique interviennent et interagissent sur la majorité des problèmes combinatoires et algorithmiques liés à l'étude des molécules d'ARN :
Une molécule d'ARN est constituée d'une succession de nucléotides A, C, G et U. Cependant, contrairement à l'ADN qui est généralement dans une configuration en double brin, la plupart des molécules d'ARN ont un brin unique. Des liaisons se forment donc entre les nucléotides selon leurs affinités physico-chimiques. Les liaisons les plus courantes sont les appariements A-U et C-G, dites ``Watson-Crick''. Il existe cependant plusieurs dizaines d'autres types de liaisons possibles entre les différents nucléotides [18,17]. La molécule d'ARN adopte dans l'espace une conformation complexe qui dépend de ces interactions et qui détermine, en grande partie, la ou les fonctions de la molécule dans la cellule. Cette structure spatiale est la structure tertiaire de la molécule. Déterminer cette structure à partir de la séquence est un problème que l'on est encore loin de savoir résoudre à l'heure actuelle. D'un autre côté, on a déterminé expérimentalement, par cristallographie, la structure tertiaire de quelques dizaines de molécules d'ARN, et de là on sait déduire les liaisons existantes entre les nucléotides [17]. On modélise la topologie d'une structure par un graphe dont les sommets sont les nucléotides. Les liaisons sont représentées par des arcs ou des arêtes, selon qu'elles sont orientées ou non. Les liaisons formant la séquence primaire sont orientées, elles définissent un chemin hamiltonien dans le graphe. Les liaisons Watson-Crick ne sont pas orientées.
Une structure secondaire d'une séquence d'ARN est une représentation partielle de sa structure tertiaire. Généralement on convient qu'une structure secondaire ne contient que les liaisons de la séquence primaire et les liaisons Watson-Crick, et que son graphe est planaire. On dit qu'une structure secondaire ne contient pas de pseudo-noeud si elle peut être dessinée sur un plan en positionnant toutes les arêtes d'un même côté du chemin hamiltonien sans que deux arêtes ne se croisent. Une structure secondaire a l'avantage d'être bien plus aisément manipulable que la structure tertiaire, tout en contenant une quantité d'informations suffisante pour un certain nombre de traitements. Actuellement, les algorithmes de prédiction de structure se bornent à essayer de déterminer la structure secondaire.
Le premier algorithme de prédiction d'une structure secondaire ab initio, c'est-à-dire sans autre donnée que la séquence, a été développé par Nussinov et al. [22] en 1978. Il s'agissait d'un algorithme de programmation dynamique visant à sélectionner la structure comportant le maximum d'appariements. La plupart des algorithmes qui ont suivi sont basés sur le même principe de programmation dynamique ; cependant la fonction à optimiser, plus réaliste, est basée sur un calcul d'énergie de la structure, approximée à partir de données expérimentales. L'algorithme le plus utilisé aujourd'hui est probablement celui de Zuker [38,36] ; il est notamment implémenté dans les logiciels mfold [37] et The Vienna RNA package [14]. Fabrice Lefebvre a montré que le concept de grammaire formelle donne une vision unificatrice des algorithmes de prédiction de structure [16]. Tous ces algorithmes prédisent des structures secondaires sans pseudo-n2#2uds. D'un autre côté, qulques auteurs ont présenté des algorithmes de prédiction de structures avec pseudo-n2#2uds, comme Akutsu [1] et Rivas et Eddy [24,25], ces derniers s'inspirant du formalisme grammatical de Lefebvre. Bien que ces algorithmes témoignent d'une avancée théorique, ils sont en pratique inapplicables du fait de leur complexité très forte (bien que polynomiale) et du peu de données expérimentales concernant l'énergie des structures complexes (comportant des pseudo-n2#2uds). Les algorithmes qui ne prennent pas les pseudo-n2#2uds en compte ont une meilleure complexité, mais leurs résultats sont encore loin d'être réellement satisfaisants. Ainsi, une étude effectuée en 1999 montre que l'algorithme de Zuker retrouve en moyenne seulement 73% des appariements avérés sur les ARN de moins de 700 bases, et vraisemblablement encore moins au-delà [20]. Les recherches visant à améliorer les prédictions sont très actives. L'équipe du LIX a récemment développé un algorithme de prédiction ayant pour principe la recherche de structures super-optimales [33]. Il existe d'autres types d'approches pour ce même problème ; notamment, en France, les travaux de Christine Gaspin [11] et ceux d'Hervé Isambert [15].
Une problématique un peu différente consiste à déterminer la structure commune à plusieurs séquences dont on suppose qu'elles ont des conformations similaires parce qu'elles sont homologues. La prise en compte de ces informations supplémentaires permet bien sûr de faire des prédictions plus fiables que dans l'approche précédente. D'un autre côté, on ne dispose pas toujours d'ensembles de séquences homologues ; et celles-ci doivent être ``bien choisies'', de façon à posséder effectivement une structure commune tout en étant assez différentes pour que l'inférence de structure soit possible. L'équipe du LaMI travaille sur une telle approche pour la prédiction de structures avec pseudo-n2#2uds [29,28] et développe les logiciels DCFold et P-DCFold. On développe au LIFL des algorithmes de prédiction qui donnent des résultats satisfaisants avec un petit nombre de séquences seulement, à partir de deux séquences [23]. Ces travaux sont implémentés dans le logiciel CARNAC.
La problématique de la comparaison est liée à celle de la prédiction, dans le contexte de la deuxième problématique ci-dessus : savoir comparer finement des structures peut permettre de les prédire plus précisément. Cependant l'application principale de la comparaison de structures réside dans le domaine de la phylogénie moléculaire, où l'on reconstitue ``l'histoire du vivant'' à partir de distances évolutives calculées entre des séquences homologues.
Dans ce cadre, les structures secondaires sont généralement modélisées par des arbres étiquetés [26,35], et les distances entre deux ou plusieurs arbres sont calculées par des algorithmes de programmation dynamique. Au sein du groupe, cinq équipes travaillent sur ce thème. D'un point de vue strictement algorithmique, les équipes du LaBRI et du LIFL ont étudié de manière très précise la complexité moyenne des algorithmes classiquement utilisés pour la comparaison d'arbres [9,10]. D'autre part, l'équipe de l'IRIN a démontré la NP-complétude d'un problème de comparaison [5], répondant ainsi à un problème ouvert posé par Wang et Zhang en 2001 [34].
Le groupe travaille aussi dans le but de rendre les algorithmes et les représentations des données plus proches de la réalité biologique. Les équipes du LaBRI et du LIFL ont proposé des variantes des algorithmes classiques, conçues de façon à tenir compte de plus de contraintes biologiques que les algorithmes classiques [8,30]. Les équipes de Lyon/Marne-la-Vallée et de Bordeaux modélisent les structures simultanément selon plusieurs ``niveaux de granularité'', pour améliorer à la fois la vitesse et la précision des algorithmes. Un logiciel, MiGAL, est en cours de développement à Marne-la-Vallée. Parallèlement, un travail sur la conception de matrices de substitution spécifiques aux structures d'ARN a été entamé dans une collaboration entre Bordeaux et les deux laboratoires d'Orsay (IGM et LRI). Ce travail permettra de pondérer plus finement les opérations d'édition de structures utilisées dans les algorithmes.
Cette thématique regroupe en fait deux types de travaux différents, selon que l'on cherche des motifs dans des séquences ou dans des structures.
Dans le premier cas, il s'agit de rechercher, dans une séquence d'ARN, un motif qui est susceptible de se replier similairement à une structure d'ARN donnée. Ce problème a pour application la recherche de structures liées à une fonction particulière. Des heuristiques générales ont été développées et implémentées, par exemple dans PALINGOL [4] et dans RNAMot [19]. Le groupe travaille sur cette problématique à la fois d'un point de vue théorique et d'un point de vue applicatif. Pendant sa thèse au LIAFA, Stéphane Vialette (LRI) a démontré précisément que, selon les contraintes que l'on se donne sur les motifs, le problème de recherche est polynomial ou NP-complet [32]. Des prolongements à ce travail sont en cours d'étude, en collaboration entre le LRI et l'IRIN. D'un autre côté, on développe au LRI et à l'IGM d'Orsay une méthode de prédiction de gènes soumis au ```décalage de traduction en -1'' [3]. Ce travail fait appel à la recherche de motifs structurels particuliers dans les séquences d'ARN messagers.
Dans le second cas, la recherche de motifs s'effectue non pas dans une séquence mais dans une structure d'ARN déjà connue. Celle-ci est modélisée par un graphe. Ce type de problème est étudié depuis quelques années à Montréal dans l'équipe de François Major, en collaboration avec Daniel Gautheret [12,13]. Dans la lignée de ces travaux, le LRI a entamé en 2003 une collaboration avec ces deux équipes sur la recherche de motifs signifiants dans une structure d'ARN, dans un esprit similaire à la problématique très féconde de la recherche de motifs sur- ou sous-représentés dans les séquences d'ADN. Dans notre cas, les motifs sont des sous graphes de graphes d'ARN, ce qui rend le problème bien plus complexe que dans les séquences.
Les structures secondaires sans pseudo-noeuds sont des structures assez simples pour pouvoir être modélisées par les mots d'un langage algébrique proche du langage de Dyck. Cette représentation fut utilisée dans les années 1980 pour résoudre des problèmes de dénombrement par Vauchaussade et Viennot [31] et a été récemment reprise par Nebel [21] Naturellement, ces mêmes structures secondaires peuvent aussi être représentées par des arbres. D'autre part, les structures tertiaires sont modélisées, on l'a vu, par des graphes hamiltoniens. Ces divers modèles sont utilisés et examinés dans le cadre de l'algorithmique des structures. Ainsi par exemple, diverses variantes de modélisation par des arbres, à plusieurs niveaux de précision, sont étudiées dans le cadre de la comparaison des structures secondaires.
Nous nous intéressons aussi à la conception de modèles de structures aléatoires, généralisant ainsi la démarche couramment adoptée dans le cadre de l'analyse des séquences. Les séquences aléatoires sont couramment utilisées pour aider à la découverte de nouvelles propriétés, en comparant les propriétés de séquences aléatoires avec des propriétés observées sur des séquences réelles. Des différences observées, on déduit des faits biologiques. En quelque sorte, les séquences aléatoires représentent le ``bruit de fond'' à partir duquel, par contraste, on cherche à déterminer quels sont les éléments biologiquement pertinents dans les séquences réelles. Pour concevoir des structures aléatoires adéquates, il faut ajouter des paramètres structurels aux paramètres statistiques couramment utilisés pour les séquences. Le concept de grammaire algébrique pondérée a été développé dans ce but au LRI et à l'IGM Orsay [6], et le logiciel GenRGenS est fondé en partie sur ce travail. Des structures d'ARN aléatoires sont destinées à être employées au sein du groupe d'une part pour étalonner et évaluer les algorithmes de comparaison (section 1.4), d'autre part pour déterminer quels sont les motifs structurels signifiants dans les structures d'ARN (section 1.5). Dans ce dernier cas, la modélisation doit aller au-delà du cadre des langages algébriques.
Il existe un certain nombre de logiciels de visualisation de structures d'ARN. Ceux qui concernent les structures tertiaires prennent en entrée les coordonnées atomiques des structures et les reproduisent fidèlement ; ils n'ont pas de difficulté particulière à résoudre d'un point de vue strictement algorithmique. En revanche, la représentation des structures secondaires (avec ou sans pseudo-noeuds) de façon claire et esthétique est un problème délicat, comme la plupart des problèmes de dessin de graphes. Il ne s'agit pas nécessairement de représenter une structure de façon ``réaliste'', mais plutôt de façon intelligible et manipulable. A ce jour, aucun programme existant ne donne pleinement satisfaction. De plus, les développements du groupe créent des besoins spécifiques dans le domaine. On aimerait en effet visualiser non seulement une structure d'ARN, mais aussi, par exemple, le résultat de la comparaison de deux ou plusieurs structures.
Des travaux dans ce sens sont réalisés au LaBRI dans le cadre du projet Tulip qui vise généralement à fournir des outils de visualisation de graphes [2]. Depuis plus récemment, le LRI se penche sur le problème de la représentation de structures avec pseudo-noeuds, en utilisant une approche ``partiellement tridimensionnelle''.
Cette action spécifique a rassemblé des équipes qui travaillaient sur l'ARN, généralement depuis peu de temps. Le volume des publications et réalisations logicielles témoigne du dynamisme de chacune des équipes dans le domaine. Elles bénéficient de contacts et collaborations sur le sujet avec d'autres groupes en France, en informatique, en biologie et en mathématiques, et à l'étranger : universités de Montréal (Canada), d'Uppsala (Suède), de Trente (Italie) et le groupe de recherche de Celera Genomics aux (Etats-Unis).
L'action a eu un effet très positif en ce qui concerne les synergies qui se sont créées au sein du groupe. On note ainsi que des liens se sont créés ou ont été renforcés grâce à l'action. Les collaborations entre LaBRI, LIFL, BBE, IGM, IRIN et LRI autour de la comparaison de structures en sont une belle illustration. Elles se concrétisent notamment par une thèse en cotutelle qui vient de commencer entre le LaBRI et le LRI.
Une communauté active et soudée s'est créée dans le département STIC et tous les partenaires de l'action sont extrêmement favorables à ce que le groupe soit pérennisé d'une façon ou d'une autre. Nous pensons qu'il pourrait certainement bénéficier d'un élargissement à d'autres laboratoires, et nous prenons des contacts dans ce sens. Nous pensons à des partenaires en informatique et en bioinformatique (INRIA et INRA), en mathématiques et en physique, mais aussi et surtout en direction des biologistes, particulièrement des biologistes expérimentalistes spécialistes de l'ARN et des phénomènes qui le touchent. Il est en effet nécessaire d'une part de confronter nos modèles et résultats à la réalité biologique, d'autre part de porter nos concepts et outils à la disposition de la communauté des biologistes. Nous visons un élargissement peut-être national dans un premier temps, mais envisageons de le généraliser, à terme, à l'Europe voire plus.
La somme allouée à l'AS, d'un montant de 30500 euros, a été partagée par le CNRS entre les cinq équipes présentes lors de la création du groupe (BBE, LaBRI, LaMI, LIFL, LRI) à raison de 6100 euros par équipe. Elle a été utilisée pour les raisons suivantes (le pourcentage indique la fraction du budget utilisée pour chaque rubrique).
Les transparents des exposés sont visibles sur le site de l'action.
Première réunion : mercredi 19 et jeudi 20 mars 2003 au LRI Orsay.
Seconde réunion : jeudi 9 novembre 2003 au LaBRI, Bordeaux.
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.
Serge Dulucq and Laurent Tichit. RNA secondary structure comparison: exact analysis of the Zhang-Shasha tree edit algorithm. Theoretical Computer Science 306 no 1-3, pp 471-484, 2003
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.
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. Bioinformatics 18 (2002) 250-259.
M. Bekaert, J.P. Forest, L. Bidou, A. Denise, G. Duchateau Nguyen, C. Fabret, C. Froidevaux, I. Hatin, J.-P. Rousset and M. Termier. Searching the Saccharomyces cerevisiae genome for -1 frameshifting sites. Proc. ECCB 2003, (European Conference on Computational Biology), September 2003, Paris, pp 4-6.
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, 2676, pp 83-95.
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.
Stéphane Vialette. Pattern Matching Problems over 2-Interval Sets. In proceedings of Combinatorial Pattern Matching, 13th Annual Symposium, CPM 2002, Fukuoka, Japan, July 3-5, 2002. Lecture Notes in Computer Science 2373, 53-63
Guillaume Blin, Guillaume Fertin, Irena Rusu et Christine Sinoquet. RNA Sequences and the EDIT(NESTED,NESTED) Problem. Rapport de Recherche RR-IRIN-03.07 de l'IRIN, soumis à publication (2003).
Guillaume Blin, Guillaume Fertin et Stéphane Vialette. A polynomial algorithm for the 2-interval pattern problem. Poster présenté au 3rd Workshop on Algorithms in Bioinformatics (WABI 2003), Septembre 2003.
Alain Denise, Yann Ponty and Michel Termier. Random generation of structured genomic sequences. Poster présenté à RECOMB 2003, April 2003, Berlin.
Yann Ponty. GenRGenS: génération aléatoire de séquences génomiques. Poster presenté à JOBIM 2002, Juin 2002, Sait-Malo.
F. Tahi, S. Engelen, M. Régnier. P-DCFold: an algorithm for RNA secondary structure prediction including all kinds of pseudoknots. Poster présenté à ECCB 2003, European Conference on Computational Biology, 27-30 septembre 2003, Paris, France.
F. Tahi, S. Engelen, M. Régnier. P-DCFold, an algorithm for RNA secondary structure prediction including all kinds of pseudoknots. Poster présenté à RECOMB 2003, International Conference on Computational Biolology, 10-13 avril 2003, Berlin, Allemagne. Currents in Computational Molecular Biology 2003, pages 363-364, 2003.
Olivier Perriquet. Algorithmes pour la prediction de structures d'ARN. Thèse de l'université de Lille, soutenue en décembre 2003. Jury : Max Dauchet, Serge Dulucq (rapporteur), Daniel Gautheret (rapporteur), Rémi Gilleron, Marie-France Sagot, Hélène Touzet (directeur).
Laurent Tichit. Algorithmique des structures biologiques : l'édition d'arborescences pour la comparaison de structures secondaires d'ARN. thèse de l'université Bordeaux I, soutenue le 19 septembre 2003. Jury : Maylis Delest, Alain Denise (rapporteur), Serge Dulucq (directeur), Jean-Marc Fédou (rapporteur), Laurent Ferraro, Michel Termier.
CARNAC (Computer Alignment of RNA by Cofolding). CARNAC est une nouvelle méthode pour la prédiction de la structure secondaire d'une famille d'ARN homologues. CARNAC fonctionne à partir de deux séquences. Il prend en entrée les séquences non alignées et produit une structure consensus par séquence. L'algorithme s'applique aussi bien à de longues séquences bien conservées (16S ssu rRNA), qu'à des familles plus hétérogènes (RNase P).
GenRGenS (Generation of Random Genomic Sequences and Structures). Un
outil de modélisation et de génération aléatoire de séquences et de
structures génomiques, selon des formalismes statistiques (chaînes de
Markov) et grammaticaux (grammaires algébriques pondérées). Permet
d'engendrer notamment des structures secondaires d'ARN aléatoires.
MiGAL. Comparaison de structures secondaires d'ARN.
DCFold (Divid and Conquer Fold) et P-DCFold
(Pseudoknots-DCfold). DCfold est un logiciel de prédiction de
structure secondaire des ARN implémentant la méthode comparative. A
partir d'alignement de séquences d'ARN homologues aux formats Fasta ou
ClustalW, on obtient en sortie un fichier au format Rnaviz. Une
extension appelée P-DCfold permet en plus de prédire des structures
contenant des pseudonoeuds.
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 rapportASARN.tex
The translation was initiated by Alain Denise on 2004-03-19