@inproceedings{3d5f548136214ca0a3cc92e88fe6417a,
title = "Space-Efficient Merging of Succinct de Bruijn Graphs",
abstract = "We propose a new algorithm for merging succinct representations of de Bruijn graphs introduced in [Bowe et al. WABI 2012]. Our algorithm is based on the lightweight BWT merging approach by Holt and McMillan [Bionformatics 2014, ACM-BCB 2014]. Our algorithm has the same asymptotic cost of the state of the art tool for the same problem presented by Muggli et al. [bioRxiv 2017, Bioinformatics 2019], 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.",
keywords = "Colored graphs, External memory algorithms, Merging, Succinct data structures, Variable-order, de Bruijn graphs",
author = "Lavinia Egidi and Louza, {Felipe A.} and Giovanni Manzini",
note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019 ; Conference date: 07-10-2019 Through 09-10-2019",
year = "2019",
doi = "10.1007/978-3-030-32686-9_24",
language = "English",
isbn = "9783030326852",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "SPRINGER",
pages = "337--351",
editor = "Brisaboa, {Nieves R.} and Puglisi, {Simon J.}",
booktitle = "String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings",
}