We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Faster Quick Search Algorithm.
- Authors
Jie Lin; Adjeroh, Donald; Yue Jiang
- Abstract
We present the FQS (faster quick search) algorithm, an improved variation of the quick search algorithm. The quick search (QS) exact pattern matching algorithm and its variants are among the fastest practical matching algorithms today. The FQS algorithm computes a statistically expected shift value, which allows maximal shifts and a smaller number of comparisons between the pattern and the text. Compared to the state-of-the-art QS variants of exact pattern matching algorithms, the proposed FQS algorithm is the fastest when |Σ| ≤ 128, where |Σ| is the alphabet size. FQS also has a competitive running time when |Σ| > 128. Running on three practical text files, E. coli (|Σ| = 4), Bible (|Σ| = 63) and World192 (|Σ| = 94), FQS resulted in the best performance in practice. Our FQS algorithm will have important applications in the domain of genomic database searching, involving DNA or RNA sequence databases with four symbols Σ = {A; C; G; T(=U)} or protein databases with |Σ| = 20.
- Subjects
SEARCH algorithms; COMPUTER algorithms; MATCHING theory; NUCLEOTIDE sequence; SEARCH engines
- Publication
Algorithms, 2014, Vol 7, Issue 2, p253
- ISSN
1999-4893
- Publication type
Article
- DOI
10.3390/a7020253