Bidirectional Variable-Order de Bruijn Graphs

Simple item page
dc.contributor.authorBelazzougui, Djamal
dc.contributor.authorGagie, Travis
dc.contributor.authorMäkinen, Veli
dc.contributor.authorPrevitali, Marco
dc.contributor.authorPuglisi, Simon J.
dc.date.accessioned2019-01-04T08:07:49Z
dc.date.available2019-01-04T08:07:49Z
dc.date.issued2018-12
dc.description.abstractCompressed suffix trees and bidirectional FM-indexes can store a set of strings and support queries that let us explore the set of substrings they contain, adding and deleting characters on both the left and right, but they can use much more space than a de Bruijn graph for the strings. Bowe et al.’s BWT-based de Bruijn graph representation (Proc. Workshop on Algorithms for Bioinformatics, pp. 225–235, 2012) can be made bidirectional as well, at the cost of increasing its space usage by a small constant, but it fixes the length of the substrings. Boucher et al. (Proc. Data Compression Conference, pp. 383–392, 2015) generalized Bowe et al.’s representation to support queries about variable-length substrings, but at the cost of bidirectionality. In this paper we show how to make Boucher et al.’s variable-order implementation of de Bruijn graphs bidirectional.fr_FR
dc.identifier.issn0129-0541fr_FR
dc.identifier.issn1793-6373fr_FR
dc.identifier.urihttp://dl.cerist.dz/handle/CERIST/932
dc.publisherWorld Scientific Publishingfr_FR
dc.relation.ispartofseriesInternational Journal of Foundations of Computer Science;29(8)
dc.relation.pages1279–1295fr_FR
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)fr_FR
dc.subjectde Bruijn graphsfr_FR
dc.subjectBurrows-Wheeler transformfr_FR
dc.subjectbidirectional FM-indexfr_FR
dc.titleBidirectional Variable-Order de Bruijn Graphsfr_FR
dc.typeArticle
Files
Collections
International Journal Papers