Hybrid indexes for repetitive datasets

H. Ferrada, T. Gagie*, T. Hirvola, S. J. Puglisi

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

18 Citations (Scopus)

Abstract

Advances in DNA sequencing mean that databases of thousands of human genomes will soon be commonplace. In this paper, we introduce a simple technique for reducing the size of conventional indexes on such highly repetitive texts. Given upper bounds on pattern lengths and edit distances, we preprocess the text with the lossless data compression algorithm LZ77 to obtain a filtered text, for which we store a conventional index. Later, given a query, we find all matches in the filtered text, then use their positions and the structure of the LZ77 parse to find all matches in the original text. Our experiments show that this also significantly reduces query times.

Original languageEnglish
Article number20130137
Number of pages9
JournalPHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A: MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES
Volume372
Issue number2016
DOIs
Publication statusPublished - 28 May 2014
MoE publication typeA1 Journal article-refereed

Keywords

  • Approximate pattern matching
  • Indexing
  • LZ77

Fingerprint Dive into the research topics of 'Hybrid indexes for repetitive datasets'. Together they form a unique fingerprint.

Cite this