Abstract
High-throughput DNA sequencing data is accumulating in public repositories, and efficient approaches for storing and indexing such data are in high demand. In recent research, several graph data structures have been proposed to represent large sets of sequencing data and allow for efficient query of sequences. In particular, the concept of colored de Bruijn graphs has been explored by several groups. While there has been good progress towards representing the sequence graph in small space, methods for storing a set of labels on top of such graphs are still not sufficiently explored. It is also currently not clear how characteristics of the input data, such as the sparsity and correlations of labels, can help to inform the choice of method to compress the labels. In this work, we present a systematic analysis of five different state-of-the-art annotation compression schemes that evaluates key metrics on both artificial and real-world data and discusses how different data characteristics influence the compression performance. In addition, we present a new approach, Multi-BRWT, that shows an up to 50% improvement in compression performance over the current state-of-the-art and is adaptive to different kinds of input data. Using our comprehensive test datasets, we show that this improvement can be robustly reproduced for different representative real-world datasets. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000314581Publikationsstatus
publishedExterne Links
Zeitschrift / Serie
bioRxivVerlag
Cold Spring Harbor LaboratoryThema
Sparse binary matrices; Binary relations; Genome graph annotationOrganisationseinheit
09568 - Rätsch, Gunnar / Rätsch, Gunnar
Förderung
167331 - Scalable Genome Graph Data Structures for Metagenomics and Genome Annotation (SNF)
Zugehörige Publikationen und Daten
Is previous version of: https://doi.org/10.3929/ethz-b-000393658
ETH Bibliographie
yes
Altmetrics