Journal article
Fast pattern-matching on indeterminate strings
Journal of Discrete Algorithms, Vol.6(1), pp.37-50
2008
Abstract
In a string x on an alphabet Σ, a position i is said to be indeterminate iff x[i] may be any one of a specified subset {λ1,λ2,…,λj} of Σ , 2⩽j⩽|Σ|. A string x containing indeterminate positions is therefore also said to be indeterminate . Indeterminate strings can arise in DNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe fast algorithms for finding all occurrences of a pattern p=p[1..m] in a given text x=x[1..n], where either or both of p and x can be indeterminate. Our algorithms are based on the Sunday variant of the Boyer–Moore pattern-matching algorithm, one of the fastest exact pattern-matching algorithms known. The methodology we describe applies more generally to all variants of Boyer–Moore (such as Horspool's, for example) that depend only on calculation of the δ (“rightmost shift”) array: our method therefore assumes that Σ is indexed (essentially, an integer alphabet), a requirement normally satisfied in practice.
Details
- Title
- Fast pattern-matching on indeterminate strings
- Authors/Creators
- J. Holub (Author/Creator)W.F. Smyth (Author/Creator)S. Wang (Author/Creator)
- Publication Details
- Journal of Discrete Algorithms, Vol.6(1), pp.37-50
- Publisher
- Elsevier
- Identifiers
- 991005545168407891
- Copyright
- © 2006 Elsevier B.V.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
47 Record Views