(*équipes intégrées à l'action après le
démarrage.)
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.
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.