Hélène Touzet (www) et Mathieu Giraud (www)Filière SCALE (systèmes complexes et algorithmes)
Equipe Bioinfo - Sequoia
LIFL - bâtiment M3
touzet[AT]lifl[DOT]fr, giraud[AT]lifl[DOT]fr
Les ARN (acides ribonucléiques) sont des molécules dont les fonctions dans la cellule sont à la fois essentielles et multiples. Ils servent notamment d'intermédiaire à l'ADN (acide désoxyribonucléique) dans la synthèse des protéines. Il existe également un grand nombre d'ARN non-codants, qui ne sont pas traduits en protéines et qui participent à de nombreux mécanismes moléculaires, tels que la régulation de l'expression des gènes. Ces ARN sont fonctionnels par eux-mêmes. Leur fonction est en grande partie déterminée par la structure spatiale de la molécule formée par des appariements entre les nucléotides.
Un problème important de l'analyse des ARN non-codants est la recherche d'ARN : étant donné un ARN non-codant décrit par sa structure, il s'agit de localiser sur une séquence les occurrences potentielles de cet ARN. Cette question pose de nouvelles questions algorithmiques, car les motifs recherchés sont des motifs structurés.
Le premier but du stage est de dresser un état de l'art des méthodes existantes de recherches d'ARN et de descripteurs d'ARN. les références [1-5] sont des bons points de départ. Le second objectif est la recherche et l'évaluation de structures d'indexation adaptées au problème de recherche d'ARN. De tels index (tables de hachage, arbres et vecteurs de suffixes, oracles...) sont classiques pour les recherches de motifs non structurés. Pour l'ARN, cet index doit permettre la recherche de motifs structurés. Peu de résultats existent à ce sujet [6]. Les tiges peuvent être un élément de base servant à l'indexation.
En cas de succès, de nombreuses perspectives seraient ouvertes, comme la comparaisons de génomes entiers sur les ARN non codants. Enfin, une bonne structure d'indexation permettrait d'inférer des motifs à partir d'une ou de plusieurs séquences, ce qui rapprocherait le problème de la recherche de motifs structuraux de celui de la découverte de structures.
Ce travail peut être poursuivi en thèse.