Efficient Compression and Indexing for Highly Repetitive DNA Sequence Collections

In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection \mathcal {G} G of t t sequences \mathcal {S}_{i} Si of length n n each, we can represent \mathcal {G} G succinctly in 2n\mathcal {H}_{k}(\mathcal {T}) + \m...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on computational biology and bioinformatics 2021-11, Vol.18 (6), p.2394-2408
Main Authors: Huo, Hongwei, Chen, Xiaoyang, Guo, Xu, Vitter, Jeffrey Scott
Format: Article
Language:English
Subjects:
Algorithms
compressed data structures
Compression
Computational Biology - methods
Data Compression - methods
Data structures
Deoxyribonucleic acid
DNA
Dynamic programming
Entropy
Indexing
Nucleotide sequence
Repetitive DNA sequences
Repetitive Sequences, Nucleic Acid - genetics
retrieval
Sequence Analysis, DNA - methods
Sequential analysis
Source code
string searching
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection \mathcal {G} G of t t sequences \mathcal {S}_{i} Si of length n n each, we can represent \mathcal {G} G succinctly in 2n\mathcal {H}_{k}(\mathcal {T}) + \mathcal {O}(n^{\prime }\ {\log \log n}) + o(q n^{\prime }) + o(tn) 2nHk(T)+O(n'loglogn)+o(qn')+o(tn) bits using \mathcal {O}(t n^{2} + q n^{\prime }) O(tn2
ISSN:1545-5963
1557-9964
DOI:10.1109/TCBB.2020.2968323