The kFM-index

Compact representation of de Bruijn subgraphs of k-mers

A du Bruijn subgraph storing the 4-mer composition of two sequences, with the stored and induced data of the kFM-index.

The kFM-index provides a compact storage of de Bruijn subgraphs representing the k-subwords of a set of strings. The intended use is the representation of the k-mer composition of sequence reads from high throughput sequencing.

The details of the data structure and algorithms for using it are included in the article published in BMC Bioinformatics, but here is a brief explanation of the data structure.

Java implementation

Download page for downloading the Java implementation and more detailed documentation of the implementation.

Updated Benchmarks for the implementation.

Last modified March 03, 2014.