moteur de recherche

Séminaire Algo - Tom Davot
Séminaire Algo - Tom Davot
23-Nov-2021 14:00
Age: 9 days

Tom Davot

On a Greedy Approach for Genome Scaffolding

Building Copernic, seminar room (4B125)

Abstract : Scaffolding is a bioinformatics problem aimed at completing the contig assembly process by determining the relative position and orientation of these contigs. It can be seen as a paths and cycles cover problem of a particular graph called the “scaffold graph”. In this talk, we provide some complexity results on this problem. We also adapt a greedy approximation algorithm on complete graphs so that it works on a special class aiming to be close to real instances. The described algorithm is the first polynomial-time approximation algorithm designed for this problem on non-complete graphs.

<- Back to: Accueil