Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Problèmes de linéarisation/circularisation de graphes et hypergraphes motivés par l'assemblage de génomes
du groupe GT Graphes et Applications

Date 2013-02-01  14:00-15:00
TitreProblèmes de linéarisation/circularisation de graphes et hypergraphes motivés par l'assemblage de génomes 
Résumé L'assemblage de génomes à partir de données de séquençage comporte deux phases : le calcul de segments génomiques (contigs), en général non-chevauchants, le calcul de l'organisation (ordre relatif) et de l'orientation de ces contigs le long du ou des chromosome(s). Cette seconde étape, le scaffolding (échafaudage) repose sur la données de lien entre paires ou groupes de contigs et l'approche classique consiste à rechercher une organisation/orientation qui est supportée par le plus grand nombre de liens. Je vais décrire la modélisation de ce problème en termes de graphes et d'hypergraphes, ainsi que des résultats positifs (algorithmes) et négatifs (preuves de NP-complétude) que nous avons récemment obtenus sur ce sujet, ainsi que quelques questions sur lesquelles nous progressons lentement. Travail en collaboration avec Ashok Rajaraman (SFU), Eric Tannier (INRIA Lyon), Murray Patterson (SFU/UBC/Lyon), Jano Manuch (UBC/SFU) et Roland Wittler (Bielefeld).  
LieuSalle 178 
OrateurCédric Chauve 



Aucun document lié à cet événement.

Retour
Retour à l'index