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.[$

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.[$