[see all job offers]
Equipe de Recherche
Equipe de bio-informatique SEQUOIAL'é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.
LIFL, Université Lille 1 / INRIA Lille Nord-Europe
Encadrants, coordonnées
Jean-Stéphane Varré (www)
jean-stephane.varre [@] lifl.fr, 03 59 57 79 18
Contexte scientifique
Un des aspects de l'étude de l'évolution des génomes consiste à retracer l'histoire de l'organisation des gènes au cours du temps. Les génomes sont représentés par des séquences de nombres représentants les gènes. Un même nombre peut-être présent plusieurs fois si le gène a été dupliqué.
Au cours du temps des modifications vont se produire et l'ordre des gènes va changer. Par exemple un segment va se trouver inversé ou bien transposé à un autre endroit dans le génome ou bien encore dupliqué. Les problèmes posés sont généralement de trouver la plus courte séquences d'opérations de réarrangement permettant de passer d'un génome à un autre, ou bien de retrouver l'ensemble des opérations permettant d'expliquer l'évolution d'un ensemble d'espèce, en connaissant les relations de parenté entre les gènes.
Sujet du stage
L'étude des réarrangements génomiques avec gènes dupliqués soulève des problèmes plus difficile que sans [1]. Ces problèmes sont pourtant fondamentaux puisqu'il existe des gènes dupliqués dans la majorité des génomes. Nous nous intéresserons à l'étude de génomes dont les gènes dupliqués sont issues d'opérations de duplication en tandem, c'est-à-dire qu'une suite de gènes a été dupliquée sur place.
Le travail consistera à s'imprégner dans un premier temps des techniques mises en oeuvre pour trouver une séquence d'opérations permettant de passer d'un génome simple à un autre utilisant une opération particulière appelée DCJ [2] puis aux techniques permettant de passer d'un génome simple à un génome avec dupliqués en considérant des opérations de duplication en tandem [3].
Dans un second temps, on tentera de trouver un algorithme capable de transformer une suite de gènes quelconque en une suite de gènes où les gènes dupliqués issus d'une duplication en tandem sont regroupés. On s'interessera à la manière de réaliser cette transformation de manière parsimonieuse (avec le moins d'opérations possibles). Puis on regardera comment transformer cette duplication en une séquence où les deux parties dupliquées apparaîtront en tandem. Enfin on pourra intégrer ces deux algorithmes dans une méthode heuristique permettant de trouver un scénario de réarrangement avec duplications en tandem et inversions.
Les algorithmes pourront être testés sur des cas concrets d'analyse de génomes en collaboration avec des biologistes.
Pré-requis :
Bonnes connaissances en algorithmique. Connaissances en biologie ou bio-informatique non nécessaires mais bienvenues.
Références bibliographiques
- [1] G Blin, C Chauve, G Fertin, R Rizzi, S Vialette. Comparing Genomes with Duplications: a Computational Complexity Point of View. 2007. IEEE/ACM transactions on computational biology and bioinformatics. www
- [2] R Friedberg, A Darling, S Yancopoulos. Genome rearrangement by the double cut and join operation. 2008. Methods in Molecular Biology. www
- [3] M Bader. Sorting by reversals, block interchanges, tandem duplications, and deletions. 2009. BMC bioinformatics. www