Fully-Functional Bidirectional Burrows-Wheeler Indexes and Infinite-Order De Bruijn Graphs

Simple item page
dc.contributor.authorBelazzougui, Djamal
dc.contributor.authorCunial, Fabio
dc.date.accessioned2019-06-10T10:29:18Z
dc.date.available2019-06-10T10:29:18Z
dc.date.issued2019-06-18
dc.description.abstractGiven a string T on an alphabet of size σ, we describe a bidirectional Burrows-Wheeler index that takes O(|T| log σ) bits of space, and that supports the addition and removal of one character, on the left or right side of any substring of T, in constant time. Previously known data structures that used the same space allowed constant-time addition to any substring of T, but they could support removal only from specific substrings of T. We also describe an index that supports bidirectional addition and removal in O(log log |T|) time, and that takes a number of words proportional to the number of left and right extensions of the maximal repeats of T. We use such fully-functional indexes to implement bidirectional, frequency-aware, variable-order de Bruijn graphs with no upper bound on their order, and supporting natural criteria for increasing and decreasing the order during traversal.fr_FR
dc.identifier.isbn978-3-95977-103-0fr_FR
dc.identifier.urihttp://dl.cerist.dz/handle/CERIST/941
dc.publisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatikfr_FR
dc.relation.ispartofseries30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019);128
dc.relation.pages1-15fr_FR
dc.relation.placePisa, Italyfr_FR
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)fr_FR
dc.subjectBWTfr_FR
dc.subjectSuffix treefr_FR
dc.subjectCDAWGfr_FR
dc.subjectde Bruijn graphfr_FR
dc.subjectMaximal repeatfr_FR
dc.subjectContractionfr_FR
dc.subjectBidirectional indexfr_FR
dc.titleFully-Functional Bidirectional Burrows-Wheeler Indexes and Infinite-Order De Bruijn Graphsfr_FR
dc.typeConference paper
Files
Collections
International Conference Papers