Gk-arrays: Querying large read collections in main memory: a versatile data structure.

Philippe N., Salson M., Lecroq T., Leonard M., Commes T., Rivals E.

Please cite THIS paper if you use Gk-arrays.

Gk-arrays are a data structure to index the k-mers in a collection of reads (short sequences provided by Next Generation Sequencing machines). Similarly, the well known suffix tree is a data structure to index the (sub)words of a text. Given a parameter k, the Gk-arrays index all k-mers occurrences in the input collection of reads (given as a file with lot of short sequences, some of them can be identical, but have different names). Once the index is built and kept in memory, the program can asks queries to the index.

An example of query type, among 7 types: given a position in the collection, compute the number of reads that share this k-mer. Gk-arrays are designed to answer multiple, even numerous (thousands, millions of) queries. Compared to other possible solutions, like hash tables, Gk-arrays are efficient in terms of memory and both of construction and query time.

Reads are produced by sequencing machines in the context of genomics projects (for genome, transcriptome, epigenome, meta-genome or meta-transcriptome sequencing). Millions of reads can be in a single run, and this represents a novel challenge for indexing algorithms.

Gk-arrays accept files where all reads have the same length, but also files with reads of varying length. The files can be in FASTA/FASTQ format.

This page provides access to the code of a C++ library to build and use Gk-arrays. This code is freely available under a GPL-compliant CeCILL-C license.

For more information about the Gk-arrays project or download latest update of Gk-arrays, see Gk-arrays project website