/Exposé en français/Talk in french/
L'échafaudage est un problème en bio-informatique dont le but est de compléter le processus d'assemblage de séquences génomiques (appelées contigs) en déterminant leurs positions et orientations relatives. Ce problème peut être vu comme un problème de couverture par des cycles et des chemins d'un graphe particulier appelé "graphe d'échafaudage". Dans cette présentation, nous formulons quelques résultats sur la complexité de ce problème. Nous adaptons également un algorithme glouton, formulé originellement sur les graphes complets, afin qu'il fonctionne sur une classe particulière que nous espérons plus proche des instances réelles. Cet algorithme est le premier algorithme polynomial pour une classe différente des graphes complets.
[Tom Davot] (LIRMM)
http://www.lirmm.fr/~davot/
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .