BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:1393@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20161024T110000
DTEND;TZID=Europe/Paris:20161024T120000
DTSTAMP:20161009T090000Z
URL:https://www.i2m.univ-amu.fr/evenements/the-superstring-graph/
SUMMARY: (...): The Superstring Graph 
DESCRIPTION::  Merging words according to their overlap yields a superstrin
 g. This basic operation allows to infer long strings from a collection of 
 short pieces\, as in genome assembly. To capture a maximum of overlaps\, t
 he 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 a
 s substrings and whose sum of lengths is minimal. SCCS is used as a crucia
 l step in polynomial time approximation algorithms for the notably hard Sh
 ortest Superstring problem\, but it is solved in cubic time. The cyclic st
 rings are then cut and merged to build a linear superstring. Building on r
 ecent theoretical work\, I will present you a linear time algorithm for so
 lving SCCS based on a Eulerian graph (the Superstring Graph) that captures
  all greedy solutions in linear space.
CATEGORIES:Séminaire,Mathématiques-Évolution-Biologie
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20160327T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR