Résumé : Ce tutorial presentera seulement certaines des problematiques autour de l’analyse des genomes qui preoccupent la bioinformatique d’aujourd’hui. je toucherai trois sujets et essayerai de donner les motivations biologiques ainsi que des raisons pour les regarder avec interet d’un point de vue mathematique et algorithmique : - les biais des codons et l’analyse de l’espace des codons. Comment on peut utiliser cette information pour parler d’un espace d’organismes. l’importance de definir des nouvelles distances dans ces espaces formels pour en tirer de l’information biologique. - La dynamique des genomes : algorithmes de reconstruction du processus de rearrangement des genomes - La reconstruction des genomes et des metagenomes. Des nouvelles questions theoriques ouvertes.

Résumé : 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.

Résumé : 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.

Résumé : 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.

Résumé : 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.