Bastien Cazaux – The Superstring Graph

Carte non disponible

Date/heure
Date(s) - 24 octobre 2016

Catégories Pas de Catégories


Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of a set of input words. The Shortest Cyclic Cover of Strings (SCCS) problem asks, instead of a single linear superstring, for a set of cyclic strings that contain the words as substrings and whose sum of lengths is minimal. SCCS is used as a crucial step in polynomial time approximation algorithms for the notably hard Shortest Superstring problem, but it is solved in cubic time. The cyclic strings are then cut and merged to build a linear superstring. Building on recent theoretical work, I will present you a linear time algorithm for solving SCCS based on a Eulerian graph (the Superstring Graph) that captures all greedy solutions in linear space.[

Bastien Cazaux – The Superstring Graph

Carte non disponible

Date/heure
Date(s) - 24 octobre 2016

Catégories Pas de Catégories


Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of a set of input words. The Shortest Cyclic Cover of Strings (SCCS) problem asks, instead of a single linear superstring, for a set of cyclic strings that contain the words as substrings and whose sum of lengths is minimal. SCCS is used as a crucial step in polynomial time approximation algorithms for the notably hard Shortest Superstring problem, but it is solved in cubic time. The cyclic strings are then cut and merged to build a linear superstring. Building on recent theoretical work, I will present you a linear time algorithm for solving SCCS based on a Eulerian graph (the Superstring Graph) that captures all greedy solutions in linear space.[