Efficient Compression and Indexing for Highly Repetitive DNA Sequence Collections
- 21 January 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 18 (6) , 2394-2408
Abstract
In this paper, we focus upon the important problem of indexing and searching highly repetitive DNA sequence collections. Given a collection G of t sequences Si of length n each, we can represent G succinctly in 2nHk(T) + O(n'loglog n) + o(qn') + o(tn) bits using O(tn2 + qn') time, where Hk(T) is the k-order empirical entropy of the sequence T ∈ G that is used as the reference sequence, n' is the total number of variations between T and the sequences in G, and q is a small fixed constant. We can restore any length len substring S[sp, ..., sp + len - 1] of S ∈ G in O(ns' + len(log n)2/ log n) time and report all positions where P occurs in G in O(m·t + occ·t ·(log n)2/ log log n) time. In addition, we propose a dynamic programming method to find the variations between T and the sequences in G in a space-efficient way, with which we can build succinct structures to enable efficient search. For highly repetitive sequences, experimental results on the tested data demonstrate that the proposed method has significant advantages in space usage and retrieval time over the current state-of-the-art methods. The source code is available online.Keywords
Funding Information
- National Natural Science Foundation of China (61741215, 61373044)
- National Science Foundation (CCF-1017623)
This publication has 29 references indexed in Scilit:
- Genome compression: a novel approach for large collectionsBioinformatics, 2013
- On compressing and indexing repetitive sequencesTheoretical Computer Science, 2013
- Large-scale compression of genomic sequence databases with the Burrows–Wheeler transformBioinformatics, 2012
- GReEn: a tool for efficient compression of genome resequencing dataNucleic Acids Research, 2011
- Repetitive DNA and next-generation sequencing: computational challenges and solutionsNature Reviews Genetics, 2011
- Robust relative compression of genomes with random accessBioinformatics, 2011
- Storage and Retrieval of Highly Repetitive Sequence CollectionsJournal of Computational Biology, 2010
- Data structures and compression algorithms for genomic sequence dataBioinformatics, 2009
- Indexing compressed textJournal of the ACM, 2005
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String MatchingSIAM Journal on Computing, 2005