Quelques problemes en analyse des genomes

Alessandra Carbone - Dept. d’Informatique de l’Universite Pierre et Marie Curie et Genomique Analytique de l’INSERM-UPMC

Sur le Calcul du Nombre de Breakpoints entre deux Génomes contenant des Duplications

Guillaume FERTIN (LINA, Université de Nantes)

Soit G1 et G2 deux génomes, chacun étant représenté par une séquence ordonnée de gènes signés. Une façon de comparer ces deux génomes consiste à compter le nombre de breakpoints entre l’un et l’autre (pour le dire rapidement, un breakpoint existe entre G1 et G2 si deux gènes consécutifs de G1 ne sont pas consécutifs dans G2).

Compter le nombre de breakpoints existant entre deux génomes est une tâche algorithmiquement facile, sous la condition qu’aucun d’entre eux ne contient de gènes dupliqués.

Dans le cas contraire, il est d’abord nécessaire d’ ?tablir une correspondance gène à gène entre les gènes de G1 et ceux de G2, de façon à se ramener à une permutation ; et, parmi toutes les correspondances gène à gène existantes, on cherche celle qui minimise le nombre de breakpoints obtenus, selon le principe de parcimonie. Malheureusement, dans ce cas, le problème devient algorithmiquement difficile, même sur des classes d’instances très restreintes.

Dans cet exposé, je présenterai les divers résultats existants sur ce problème, du point de vue de la complexité algorithmique, de l’approximation, des heuristiques et même des algorithmes exacts.

Prediction de sites d’interaction de proteines par analyse d’arbres phylogenetiques

Stefan Engelen, Genomique Analytique INSERM-UPMC

Déterminer les sites d’interactions des protéines est un problème crucial notamment pour rechercher des cibles thérapeutiques. La méthode Evolutionary Trace basée sur l’analyse de l’évolution d’une protéine au travers d’un arbre phylogénétique permet d’appréhender les parties de la protéine conservées au cours de l’évolution et donc suceptibles d’être biologiquement importantes. L’exposé présentera les problématiques algorithmiques et combinatoires associées à l’analyse des arbres phylogénétiques au travers de la description d’un nouvel outil (JET) inspiré de cette méthode.

Algorithmique des structures d’ARN

Alain Denise, LRI, Paris-Sud XI

Depuis quelques années, le rôle de l’ARN dans les différents processus cellulaires a été considérablement réévalué. Il y a donc, plus que jamais, un besoin crucial d’outils informatiques pour aider à la manipulation et à la modélisation des ARN. Parmi les problèmes les plus importants, on trouve la prédiction de la structure d’une séquence d’ARN et la comparaison de deux ou plusieurs structures. L’exposé sera principalement focalisé sur la problématique de la comparaison des structures d’ARN. On y abordera notamment la complexité théorique de quelques problèmes de comparaison ainsi que des approches algorithmiques développées récemment.

Modelisation des reseaux de regulation genetiques par les reseaux de jeux

Matthieu Manceny, laboratoire MAS, Ecole Centrale Paris

La théorie des réseaux de jeux est un formalisme original de modélisation des systèmes complexes permettant de prendre en compte les interactions locales. Les réseaux de jeux se fondent sur la théorie des jeux, et étendent les jeux stratégiques en autorisant les joueurs à participer à plusieurs jeux simultanément. Les comportements locaux, décrits par les différents jeux du réseau, se combinent pour atteindre des situations d’équilibres globaux sur l’ensemble du réseau.

Le cadre applicatif des réseaux de jeux s’étend à tous les systèmes où l’étude de la localité est nécessaire à la compréhension du fonctionnement du système. Parmi ces domaines, les réseaux de régulation génétique constituent un champ privilégié. Leur étude exhibe des organisations structurelles dans le système qui sous-tendent a priori un découpage de l’activité globale du système en structures modulaires. La modélisation proposée se fonde sur la définition de jeux de régulation élémentaire (modélisant l’activation ou l’inhibition d’un gène par un autre gène) qui se combinent pour former des régulations plus complexes. Les équilibres globaux du réseau de jeux capturent alors les états stables du réseau de régulation.