[see all job offers]

Equipe de Recherche

Equipe de bio-informatique SEQUOIA
LIFL, Université Lille 1 / INRIA Lille Nord-Europe

L'équipe SEQUOIA développe des algorithmes et des logiciels pour l'analyse de séquences biologiques: ADN, ARN, protéine. Ses thèmes d'expertise sont l'alignement de séquences, les ARN noncodants, les peptides non ribosomiaux, l'organisation des génomes, la génomique comparative.

Encadrement

Hélène Touzet [www]
helene.touzet [@] lifl.fr, 03 59 57 79 16

Contexte scientifique

Les ARN non-codants sont des molécules dont les fonctions dans la cellule sont à la fois essentielles et multiples. Ils participent à de nombreux mécanismes moléculaires, tels que la régulation de l'expression des gènes. La spécificité de ces molécules est que leur fonction est en grande partie déterminée par la structure spatiale formée par des appariements entre les nucléotides. D'un point de vue combinatoire, ce sont donc des objets complexes, que l'on peut modéliser à base d'arbres, de graphes ou de grammaires.

Sujet du stage

Un problème important de l'analyse des ARN non-codants est la recherche de motifs : étant donné une familles d'ARN non-codants, il s'agit de localiser sur une séquence les occurrences potentielles de cet ARN. Les méthodes classiques, largement diffusées, utilisent des grammaires stochastiques hors contexte, ou modèles de covariance [1]. Ces modèles sont très expressifs, et assurent une bonne spécificité. Mais les algorithmes associés ont une complexité trop importante pour permettre une analyse à grande échelle [2]. Plusieurs améliorations ont récemment été proposées [3,4,5,6], sans toutefois permettre le traitement de génomes complets en un temps raisonnable.

L'objectif du stage est la construction de modèles simples pour des familles d'ARN, inférés à partir des grammaires stochastiques ou directement à partir des données de séquence (disponibles dans la banque de données RFAM, par exemple). Ces modèles pourraient être construits comme une organisation de modules indépendants, se prêtant ainsi à un filtrage sans perte très efficace.

Ce stage peut etre poursuivi en thèse. Il peut également faire l'objet d'une remunération.

Pré-requis

Formation en informatique ou en bio-informatique. Compétences en algorithmique, programmation en C

Références bibliographiques

1. Query-dependent banding (QDB) for faster RNA similarity searches, Nawrocki EP, Eddy SR, PLoS Comput Biology,3(3):e56, 2007
2. Exploring genomic dark matter: A critical assessment of the performance of homology search methods on noncoding RNA. Gardner PP. Freyhult EK, Bollback JP. Genome Research, 17:117 -- 125, 2007
3. Designing Secondary Structure Profiles for Fast ncRNA Identification. Yanni Sun, Jeremy Buhler, Computational Systems Bioinformatics 2008 [PDF]
4. Searching genomes for noncoding RNA using FastR. Shaojie Zhang Haas, B. Eskin, E. Bafna, V., Computational Biology and Bioinformatics, IEEE transactions 2(4)- 4, 366- 379, 2005
5. RNA Search with Decision Trees and Partial Covariance Models, J. A. Smith, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 6(3), pp. 517-527, 2009 [PDF]
6. Faster genome annotation of non-coding RNA families without loss of accuracy, Z. Weinberg and W.L. Ruzzo (2004), Proc. Eighth Annual Inter. Conf. on Computational Molecular Biology (RECOMB), p. 243-251. [PDF]