Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

On-Demand Indexing for Referential Compression of DNA Sequences.

ABSTRACT: The decreasing costs of genome sequencing is creating a demand for scalable storage and processing tools and techniques to deal with the large amounts of generated data. Referential compression is one of these techniques, in which the similarity between the DNA of organisms of the same or an evolutionary close species is exploited to reduce the storage demands of genome sequences up to 700 times. The general idea is to store in the compressed file only the differences between the to-be-compressed and a well-known reference sequence. In this paper, we propose a method for improving the performance of referential compression by removing the most costly phase of the process, the complete reference indexing. Our approach, called On-Demand Indexing (ODI) compresses human chromosomes five to ten times faster than other state-of-the-art tools (on average), while achieving similar compression ratios.

SUBMITTER: Alves F

PROVIDER: S-EPMC4493149 | biostudies-literature | 2015

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

On-Demand Indexing for Referential Compression of DNA Sequences.

Alves Fernando F Cogo Vinicius V Wandelt Sebastian S Leser Ulf U Bessani Alysson A

PloS one 20150706 7

The decreasing costs of genome sequencing is creating a demand for scalable storage and processing tools and techniques to deal with the large amounts of generated data. Referential compression is one of these techniques, in which the similarity between the DNA of organisms of the same or an evolutionary close species is exploited to reduce the storage demands of genome sequences up to 700 times. The general idea is to store in the compressed file only the differences between the to-be-compresse ...[more]

PMID: 26146838

Similar Datasets

Indexing labeled sequences.

Project description:BackgroundLabels are a way to add some information on a text, such as functional annotations such as genes on a DNA sequences. V(D)J recombinations are DNA recombinations involving two or three short genes in lymphocytes. Sequencing this short region (500 bp or less) produces labeled sequences and brings insight in the lymphocyte repertoire for onco-hematology or immunology studies.MethodsWe present two indexes for a text with non-overlapping labels. They store the text in a Burrows-Wheeler transform (BWT) and a compressed label sequence in a Wavelet Tree. The label sequence is taken in the order of the text (TL-index) or in the order of the BWT (TLBW-index). Both indexes need a space related to the entropy of the labeled text.ResultsThese indexes allow efficient text-label queries to count and find labeled patterns. The TLBW-index has an overhead on simple label queries but is very efficient on combined pattern-label queries. We implemented the indexes in C++ and compared them against a baseline solution on pseudo-random as well as on V(D)J labeled texts.DiscussionNew indexes such as the ones we proposed improve the way we index and query labeled texts as, for instance, lymphocyte repertoire for hematological and immunological studies.

| S-EPMC7924554 | biostudies-literature

Comment on: 'ERGC: an efficient referential genome compression algorithm'.

Project description:MotivationData compression is crucial in effective handling of genomic data. Among several recently published algorithms, ERGC seems to be surprisingly good, easily beating all of the competitors.ResultsWe evaluated ERGC and the previously proposed algorithms GDC and iDoComp, which are the ones used in the original paper for comparison, on a wide data set including 12 assemblies of human genome (instead of only four of them in the original paper). ERGC wins only when one of the genomes (referential or target) contains mixed-cased letters (which is the case for only the two Korean genomes). In all other cases ERGC is on average an order of magnitude worse than GDC and iDoComp.Contactsebastian.deorowicz@polsl.pl, iochoa@stanford.eduSupplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC4907388 | biostudies-literature

HRCM: An Efficient Hybrid Referential Compression Method for Genomic Big Data.

Project description:With the maturity of genome sequencing technology, huge amounts of sequence reads as well as assembled genomes are generating. With the explosive growth of genomic data, the storage and transmission of genomic data are facing enormous challenges. FASTA, as one of the main storage formats for genome sequences, is widely used in the Gene Bank because it eases sequence analysis and gene research and is easy to be read. Many compression methods for FASTA genome sequences have been proposed, but they still have room for improvement. For example, the compression ratio and speed are not so high and robust enough, and memory consumption is not ideal, etc. Therefore, it is of great significance to improve the efficiency, robustness, and practicability of genomic data compression to reduce the storage and transmission cost of genomic data further and promote the research and development of genomic technology. In this manuscript, a hybrid referential compression method (HRCM) for FASTA genome sequences is proposed. HRCM is a lossless compression method able to compress single sequence as well as large collections of sequences. It is implemented through three stages: sequence information extraction, sequence information matching, and sequence information encoding. A large number of experiments fully evaluated the performance of HRCM. Experimental verification shows that HRCM is superior to the best-known methods in genome batch compression. Moreover, HRCM memory consumption is relatively low and can be deployed on standard PCs.

| S-EPMC6930768 | biostudies-literature

TRCMGene: A two-step referential compression method for the efficient storage of genetic data.

Project description:BackgroundThe massive quantities of genetic data generated by high-throughput sequencing pose challenges to data storage, transmission and analyses. These problems are effectively solved through data compression, in which the size of data storage is reduced and the speed of data transmission is improved. Several options are available for compressing and storing genetic data. However, most of these options either do not provide sufficient compression rates or require a considerable length of time for decompression and loading.ResultsHere, we propose TRCMGene, a lossless genetic data compression method that uses a referential compression scheme. The novel concept of two-step compression method, which builds an index structure using K-means and k-nearest neighbours, is introduced to TRCMGene. Evaluation with several real datasets revealed that the compression factor of TRCMGene ranges from 9 to 21. TRCMGene presents a good balance between compression factor and reading time. On average, the reading time of compressed data is 60% of that of uncompressed data. Thus, TRCMGene not only saves disc space but also saves file access time and speeds up data loading. These effects collectively improve genetic data storage and transmission in the current hardware environment and render system upgrades unnecessary. TRCMGene, user manual and demos could be accessed freely from https://github.com/tangyou79/TRCM. The data mentioned in this manuscript could be downloaded from: https://github.com/tangyou79/TRCM/wiki.

| S-EPMC6218042 | biostudies-literature

Nucleotide Archival Format (NAF) enables efficient lossless reference-free compression of DNA sequences.

Project description:SummaryDNA sequence databases use compression such as gzip to reduce the required storage space and network transmission time. We describe Nucleotide Archival Format (NAF)-a new file format for lossless reference-free compression of FASTA and FASTQ-formatted nucleotide sequences. Nucleotide Archival Format compression ratio is comparable to the best DNA compressors, while providing dramatically faster decompression. We compared our format with DNA compressors: DELIMINATE and MFCompress, and with general purpose compressors: gzip, bzip2, xz, brotli and zstd.Availability and implementationNAF compressor and decompressor, as well as format specification are available at https://github.com/KirillKryukov/naf. Format specification is in public domain. Compressor and decompressor are open source under the zlib/libpng license, free for nearly any use.Supplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC6761962 | biostudies-literature

Molecular indexing of human genomic DNA.

Project description:Molecular indexing sorts DNA fragments into subsets for inter-sample comparisons. Type IIS or interrupted palindrome restriction endonucleases, which result in single-stranded ends not including the original recognition sequence of the enzyme, are used to produce the fragments. The ends can then be any sequence but will always be specific for a given fragment. Fragments with particular ends are selected by ligation to a corresponding indexing adapter. We describe iterative indexing, a new process that after an initial round of indexing uses a Type IIS restriction endonuclease to expose additional sequence for further indexing. New plasmids, pINDnn, were produced for novel use as indexing adapters. Together, the plasmids index all 16 possible dinucleotides. Their large size can be increased by dimerisation in vitro and allows the isolation of indexed material by size separation. Fragments produced from human genomic DNA by Type II restriction endonucleases were sorted using six bases in total to a possible enrichment of 1920-fold. By comparison with the public human sequence databases, fidelity of indexing was shown to be high and was tolerant of repetitive sequences. Genome-wide comparisons on a candidate or non-candidate basis are made possible by this approach.

| S-EPMC60255 | biostudies-literature

Indexing strategies for rapid searches of short words in genome sequences.

Project description:Searching for matches between large collections of short (14-30 nucleotides) words and sequence databases comprising full genomes or transcriptomes is a common task in biological sequence analysis. We investigated the performance of simple indexing strategies for handling such tasks and developed two programs, fetchGWI and tagger, that index either the database or the query set. Either strategy outperforms megablast for searches with more than 10,000 probes. FetchGWI is shown to be a versatile tool for rapidly searching multiple genomes, whose performance is limited in most cases by the speed of access to the filesystem. We have made publicly available a Web interface for searching the human, mouse, and several other genomes and transcriptomes with oligonucleotide queries.

| S-EPMC1894650 | biostudies-literature

A compression method for DNA.

Project description:The development of high-throughput sequencing technology has generated huge amounts DNA data. Many general compression algorithms are not ideal for compressing DNA data, such as the LZ77 algorithm. On the basis of Nour and Sharawi's method,we propose a new, lossless and reference-free method to increase the compression performance. The original sequences are converted into eight intermediate files and six final files. Then, the LZ77 algorithm is used to compress the six final files. The results show that the compression time is decreased by 83% and the decompression time is decreased by 54% on average.The compression rate is almost the same as Nour and Sharawi's method which is the fastest method so far. What's more, our method has a wider range of application than Nour and Sharawi's method. Compared to some very advanced compression tools at present, such as XM and FCM-Mx, the time for compression in our method is much smaller, on average decreasing the time by more than 90%.

| S-EPMC7688149 | biostudies-literature

Single-cell DNA methylation sequencing by combinatorial indexing and enzymatic DNA methylation conversion

Project description:Background DNA methylation is a critical molecular mark involved in cellular differentiation and cell-specific processes. Single-cell whole genome DNA methylation profiling methods hold great potential to resolve the DNA methylation profiles of individual cell-types. Here we present a method that couples single-cell combinatorial indexing (sci) with enzymatic conversion (sciEM) of unmethylated cytosines. Results The sciEM method facilitates DNA methylation profiling of single-cells that is highly correlated with single-cell bisulfite-based workflows (r2 > 0.99) whilst improving sequencing alignment rates, reducing adapter contamination and over-estimation of DNA methylation levels (CpG and non-CpG). As proof-of-concept we perform sciEM analysis of the temporal lobe, motor cortex, hippocampus and cerebellum of the human brain to resolve single-cell DNA methylation of all major cell-types. Conclusion To our knowledge sciEM represents the first non-bisulfite single-cell DNA methylation sequencing approach with single-base resolution. Supplementary Information The online version contains supplementary material available at 10.1186/s13578-022-00938-9.

| S-EPMC9811750 | biostudies-literature

Reference-based compression of short-read sequences using path encoding.

Project description:MotivationStoring, transmitting and archiving data produced by next-generation sequencing is a significant computational burden. New compression techniques tailored to short-read sequence data are needed.ResultsWe present here an approach to compression that reduces the difficulty of managing large-scale sequencing data. Our novel approach sits between pure reference-based compression and reference-free compression and combines much of the benefit of reference-based approaches with the flexibility of de novo encoding. Our method, called path encoding, draws a connection between storing paths in de Bruijn graphs and context-dependent arithmetic coding. Supporting this method is a system to compactly store sets of kmers that is of independent interest. We are able to encode RNA-seq reads using 3-11% of the space of the sequence in raw FASTA files, which is on average more than 34% smaller than competing approaches. We also show that even if the reference is very poorly matched to the reads that are being encoded, good compression can still be achieved.Availability and implementationSource code and binaries freely available for download at http://www.cs.cmu.edu/?ckingsf/software/pathenc/, implemented in Go and supported on Linux and Mac OS X.

| S-EPMC4481695 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data