Affordable Access

Access to the full text

Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs

Authors
  • Holley, Guillaume1
  • Melsted, Páll1
  • 1 Faculty of Industrial Engineering, Mechanical Engineering and Computer Science, University of Iceland, Reykjavík, Iceland , Reykjavík (Iceland)
Type
Published Article
Publication Date
Sep 17, 2020
Volume
21
Issue
1
Identifiers
DOI: 10.1186/s13059-020-02135-8
Source
Springer Nature
License
Green

Abstract

Memory consumption of de Bruijn graphs is often prohibitive. Most de Bruijn graph-based assemblers reduce the complexity by compacting paths into single vertices, but this is challenging as it requires the uncompacted de Bruijn graph to be available in memory. We present a parallel and memory-efficient algorithm enabling the direct construction of the compacted de Bruijn graph without producing the intermediate uncompacted graph. Bifrost features a broad range of functions, such as indexing, editing, and querying the graph, and includes a graph coloring method that maps each k-mer of the graph to the genomes it occurs in. Availability https://github.com/pmelsted/bifrost

Report this publication

Statistics

Seen <100 times