Hybrid indexes for repetitive datasets

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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

18 Sitaatiot (Scopus)

Abstrakti

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.

AlkuperäiskieliEnglanti
Artikkeli20130137
Sivumäärä9
JulkaisuPHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A: MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES
Vuosikerta372
Numero2016
DOI - pysyväislinkit
TilaJulkaistu - 28 toukokuuta 2014
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki Sukella tutkimusaiheisiin 'Hybrid indexes for repetitive datasets'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Siteeraa tätä