Konnector

Connecting Paired-end Reads Using a Bloom Filter de Bruijn Graph

Project Description

Konnector is a scalable de novo assembler for paired-end reads.

It fills in the nucleotides of the sequence gap between read pairs by navigating a de Bruijn graph (DBG) represented by a Bloom filter.

The Bloom filter is a probabilistic and memory-efficient data structure that enables storing the de Bruijn graph using a mean 1.5 bytes of memory per k-mer (our implementation), which represents a marked improvement over the typical hash table data structure employed by most DBG assemblers. The memory usage per k-mer is independent of the k-mer length, enabling application of the tool to large genomes.

The release of Konnector 2.0 introduces the ability to extend paired-end sequences outwards in the de Bruijn graph, in addition to merging reads pairs via connecting paths. 

Availability

Konnector is included with ABySS version 1.5.2 and later, and is available for download from: http://www.bcgsc.ca/platform/bioinfo/software/abyss

Citations

[1] Vandervalk, Benjamin P., Shaun D. Jackman, Anthony Raymond, Hamid Mohamadi, Chen Yang, Dean Attali, James Chu, Rene L. Warren, and Inanc Birol. "Konnector: Connecting paired-end reads using a bloom filter de Bruijn graph." In Bioinformatics and Biomedicine (BIBM), 2014 IEEE International Conference on, pp. 51-58. IEEE, 2014. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6999126&tag=1

[2] Vandervalk, Benjamin P., Chen Yang, Zhuyi Xue, Karthika Raghavan, Justin Chu, Hamid Mohamadi, Shaun D. Jackman, Readman Chiu, René L. Warren, and Inanç Birol. "Konnector v2. 0: pseudo-long reads from paired-end sequencing data." BMC medical genomics 8, no. Suppl 3 (2015): S1. http://dx.doi.org/10.1186%2F1755-8794-8-S3-S1