Compacting de Bruijn graphs from sequencing data quickly and in low memory.

ABSTRACT:

Motivation

As the quantity of data per sequencing experiment increases, the challenges of fragment assembly are becoming increasingly computational. The de Bruijn graph is a widely used data structure in fragment assembly algorithms, used to represent the information from a set of reads. Compaction is an important data reduction step in most de Bruijn graph based algorithms where long simple paths are compacted into single vertices. Compaction has recently become the bottleneck in assembly pipelines, and improving its running time and memory usage is an important problem.

Results

We present an algorithm and a tool bcalm 2 for the compaction of de Bruijn graphs. bcalm 2 is a parallel algorithm that distributes the input based on a minimizer hashing technique, allowing for goo

SUBMITTER: Chikhi R 

PROVIDER: S-EPMC4908363 | biostudies-literature | 2016 Jun

REPOSITORIES: biostudies-literature