Wyniki wyszukiwania - BazTech

1

Compact and hash based variants of the suffix array

Grabowski S., Raniszewski M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2017

|

Vol. 65, nr 4

407--418

EN

Full-text indexing aims at building a data structure over a given text capable of efficiently finding arbitrary text patterns, and possibly requiring little space. We propose two suffix array inspired full-text indexes. One, called SA-hash, augments the suffix array with a hash table to speed up pattern searches due to significantly narrowed search interval before the binary search phase. The other, called FBCSA, is a compact data structure, similar to Mäkinen’s compact suffix array (MakCSA), but working on fixed size blocks. Experiments on the widely used Pizza & Chili datasets show that SA-hash is about 2–3 times faster in pattern searches (counts) than the standard suffix array, for the price of requiring 0.2n–1.1n bytes of extra space, where n is the text length. FBCSA, in one of the presented variants, reduces the suffix array size by a factor of about 1.5–2, while it gets close in search times, winning in speed with its competitors known from the literature, MakCSA and LCSA.

2

Searching for unique DNA sequences with the Burrows-Wheeler Transform

Pokrzywa R.

Biocybernetics and Biomedical Engineering

|

2008

|

Vol. 28, no. 1

95-104

EN

The objective of this study was to present an efficient algorithm that effectively aids the problem of searching for unique DNA sequences in the set of genes. The presented algorithm is based on the Burrows-Wheeler Transform (BWT), a very fast and effective data compression algorithm. The developed algorithm exploits all the advantages offered by the BWT algorithm and the suffix array data structure. It allows obtaining a structure that is ideal for solving many problems related to the pattern-matching problem. This algorithm is applicable to the identification of yeast species as well as to many other computational molecular biology problems like searching for repetitive structures in genomic sequences, designing of DNA hybridization probes and many more.

3

Compact Suffix Array - A Space-Efficient Full-Text Index

Mäkinen V.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 1,2

191-210

EN

Suffix array is a widely used full-text index that allows fast searches on the text. It is constructed by sorting all suffixes of the text in the lexicographic order and storing pointers to the suffixes in this order. Binary search is used for fast searches on the suffix array. Compact suffix array is a compressed form of the suffix array that still allows binary searches, but the search times are also dependent on the compression. In this paper, we give efficient methods for constructing and querying compact suffix arrays. We also study practical issues, such as the trade off between compression and search times, and show how to reduce the space requirement of the construction. Experimental results are provided in comparison with other search methods. With a large text corpora, the index took 1.6 times the size of the text, while the searches were only two times slower than from a suffix array.