Evènement pour le 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