A space and time-efficient index for the compacted colored de Bruijn graph.

ABSTRACT:

Motivation

Indexing reference sequences for search-both individual genomes and collections of genomes-is an important building block for many sequence analysis tasks. Much work has been dedicated to developing full-text indices for genomic sequences, based on data structures such as the suffix array, the BWT and the FM-index. However, the de Bruijn graph, commonly used for sequence assembly, has recently been gaining attention as an indexing data structure, due to its natural ability to represent multiple references using a graphical structure, and to collapse highly-repetitive sequence regions. Yet, much less attention has been given as to how to best index such a structure, such that queries can be performed efficiently and memory usage remains practical as the size and number of

SUBMITTER: Almodaresi F 

PROVIDER: S-EPMC6022659 | biostudies-literature | 2018 Jul

REPOSITORIES: biostudies-literature