Dynamic compression schemes for graph coloring
Autor: | Carsten Eickhoff, Ingo Schilken, Harun Mustafa, André Kahles, Gunnar Rätsch, Mikhail Karasikov |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2019 |
Předmět: |
Statistics and Probability
Theoretical computer science Computer science 0206 medical engineering Color 02 engineering and technology Lossy compression External Data Representation Biochemistry 03 medical and health sciences Graph coloring Molecular Biology 030304 developmental biology Lossless compression 0303 health sciences 030302 biochemistry & molecular biology Search engine indexing Computational Biology High-Throughput Nucleotide Sequencing Bloom filter Genomics Data Compression Original Papers Graph Computer Science Applications Metadata Computational Mathematics Computational Theory and Mathematics Topological graph theory Graph (abstract data type) Sequence Analysis 020602 bioinformatics Algorithms Software |
Zdroj: | Bioinformatics, 35 (3) Bioinformatics |
ISSN: | 1367-4803 1460-2059 |
Popis: | Motivation Technological advancements in high-throughput DNA sequencing have led to an exponential growth of sequencing data being produced and stored as a byproduct of biomedical research. Despite its public availability, a majority of this data remains hard to query for the research community due to a lack of efficient data representation and indexing solutions. One of the available techniques to represent read data is a condensed form as an assembly graph. Such a representation contains all sequence information but does not store contextual information and metadata. Results We present two new approaches for a compressed representation of a graph coloring: a lossless compression scheme based on a novel application of wavelet tries as well as a highly accurate lossy compression based on a set of Bloom filters. Both strategies retain a coloring even when adding to the underlying graph topology. We present construction and merge procedures for both methods and evaluate their performance on a wide range of different datasets. By dropping the requirement of a fully lossless compression and using the topological information of the underlying graph, we can reduce memory requirements by up to three orders of magnitude. Representing individual colors as independently stored modules, our approaches can be efficiently parallelized and provide strategies for dynamic use. These properties allow for an easy upscaling to the problem sizes common to the biomedical domain. Bioinformatics, 35 (3) ISSN:1367-4803 ISSN:1460-2059 |
Databáze: | OpenAIRE |
Externí odkaz: |