A Fast Pattern Matching Algorithm for Biological Sequences
With the remarkable increase in the number of DNA and proteins sequences, it is more important for the study of pattern matching in querying sequence patterns in the biological sequence database. To further raise the performance of the pattern matching algorithm, a fast exact algorithm (called ZTBMH), which is a variation of Zhu-Takaoka algorithm, is presented. It absorbs the idea of Boyer-Moore-Horspool algorithm, which utilizes only bad character heuristic and reduces the number of comparisons, thus improves the performance in practice. The best, worst and average cases in time complexities of the new algorithm are also discussed in this paper. The experimental results show that the proposed algorithm works better than other compared algorithms, especially in case of small alphabets such as nucleotides sequences, and thus the proposed algorithm is quite applicable for exact pattern matching in biological sequences.
pattern matching algorithm biological sequences
Yong Huang Xuezeng Pan Yunjun Gao Guoyong Cai
College of Computer Science and Technology Zhejiang University Hangzhou, China College of Computer Science and Technology Guilin University of Electronic Science and Technology Gu
国际会议
上海
英文
608-611
2008-05-16（万方平台首次上网日期，不代表论文的发表时间）