Compressed 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.

Belazzougui, D., Gagie, T., Mäkinen, V., Previtali, M., Puglisi, S. (2018). Bidirectional Variable-Order de Bruijn Graphs. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 29(8), 1279-1295 [10.1142/S0129054118430037].

Bidirectional Variable-Order de Bruijn Graphs

Previtali, Marco;
2018

Abstract

Compressed 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.
Articolo in rivista - Articolo scientifico
bidirectional FM-index; Burrows-Wheeler transform; de Bruijn graphs;
de Bruijn graphs, Burrows-Wheeler transform, bidirectional FM-index
English
1279
1295
17
Belazzougui, D., Gagie, T., Mäkinen, V., Previtali, M., Puglisi, S. (2018). Bidirectional Variable-Order de Bruijn Graphs. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 29(8), 1279-1295 [10.1142/S0129054118430037].
Belazzougui, D; Gagie, T; Mäkinen, V; Previtali, M; Puglisi, S
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/215088
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
Social impact