Computer Science – Data Structures and Algorithms
Scientific paper
2011-09-13
Computer Science
Data Structures and Algorithms
Accepted to ISAAC 2011
Scientific paper
Motivated by the imminent growth of massive, highly redundant genomic databases, we study the problem of compressing a string database while simultaneously supporting fast random access, substring extraction and pattern matching to the underlying string(s). Bille et al. (2011) recently showed how, given a straight-line program with $r$ rules for a string $s$ of length $n$, we can build an $\Oh{r}$-word data structure that allows us to extract any substring (s [i..j]) in $\Oh{\log n + j - i}$ time. They also showed how, given a pattern $p$ of length $m$ and an edit distance (k \leq m), their data structure supports finding all \occ approximate matches to $p$ in $s$ in $\Oh{r (\min (m k, k^4 + m) + \log n) + \occ}$ time. Rytter (2003) and Charikar et al. (2005) showed that $r$ is always at least the number $z$ of phrases in the LZ77 parse of $s$, and gave algorithms for building straight-line programs with $\Oh{z \log n}$ rules. In this paper we give a simple $\Oh{z \log n}$-word data structure that takes the same time for substring extraction but only $\Oh{z (\min (m k, k^4 + m)) + \occ}$ time for approximate pattern matching.
Gagie Travis
Gawrychowski Pawel
Puglisi Simon J.
No associations
LandOfFree
Faster Approximate Pattern Matching in Compressed Repetitive Texts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Faster Approximate Pattern Matching in Compressed Repetitive Texts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Approximate Pattern Matching in Compressed Repetitive Texts will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-568414