Paper Info
Title
Space Efficient Merging of de Bruijn Graphs and Wheeler Graphs
Abstract
The merging of succinct data structures is a well established technique for the space efficient construction of large succinct indexes. In the first part of the paper we propose a new algorithm for merging succinct representations of de Bruijn graphs. Our algorithm has the same asymptotic cost of the state of the art algorithm for the same problem but it uses less than half of its working space. A novel important feature of our algorithm, not found in any of the existing tools, is that it can compute the Variable Order succinct representation of the union graph within the same asymptotic time/space bounds. In the second part of the paper we consider the more general problem of merging succinct representations of Wheeler graphs, a recently introduced graph family which includes as special cases de Bruijn graphs and many other known succinct indexes based on the BWT or one of its variants. In this paper we provide a space efficient algorithm for Wheeler graph merging; our algorithm works under the assumption that the union of the input Wheeler graphs has an ordering that satisfies the Wheeler conditions and which is compatible with the ordering of the original graphs.
Year
DOI
Venue
2022
10.1007/s00453-021-00855-2
Algorithmica
Keywords
DocType
Volume
Succinct data structures, de Bruijn graphs, Wheeler graphs, BWT variants, Space efficient algorithms
Journal
84
Issue
ISSN
Citations 
3
0178-4617
0
PageRank 
References 
Authors
0.34
16
3
Name
Order
Citations
PageRank
Lavinia Egidi19110.21
Felipe Alves da Louza2409.13
Giovanni Manzini31584111.42