Bidirectional Variable-Order de Bruijn Graphs
Loading...
Date
2016-03-22
Journal Title
Journal ISSN
Volume Title
Publisher
Springer International Publishing
Abstract
Implementing de Bruijn graphs compactly is an important problem because of their role in genome assembly. There are currently two main approaches, one using Bloom filters and the other using a kind of Burrows-Wheeler Transform on the edge labels of the graph. The second representation is more elegant and can even handle many graph-orders at once, but it does not cleanly support traversing edges backwards or inserting new nodes or edges. In this paper we resolve the first of these issues and partially address the second.
Description
Keywords
de Bruijn Graphs, Bidirectional navigation, Burrows-Wheeler transform, Variable order